Abstract

Tractability has been studied under many different angles, by different research communities, and by using a wide range of techniques. This two-day workshop will bring together distinguished researchers to discuss their viewpoints on the question: What makes some difficult (that is, NP-hard) problems tractable in practice?

Goal of the Workshop Tractability has been studied under many different angles, by different research communities and using a wide range of techniques. The workshop will provide a place for interactions between experts from those diverse backgrounds, including both theoreticians and practitioners. Topics explored during this workshop include:

Proof complexity Graphical properties Linear Relaxations Real-life versus random problems, instance complexity Sub-modularity and convexity Tractable approximations Fixed-parameter tractability Hybridization of techniques Tractability in knowledge representation Algebraic approaches to tractability

Workshop on Tractability / Programme Monday, July 5

09:00 registration and coffee 09:50 welcome 10:00

John Hooker. Carnegie Mellon University, U.S.A

Integrating Solution Methods through Duality

10:45 Peter Jeavons. University of Oxford, UK

Presenting Constraints

11:30 Georg Gottlob. University of Oxford, UK

Hypertree Decompositions

12:15 lunch 13:00 Joao Marques-Silva. University College Dublin, Ireland

Boolean Satisfiability Solving: Past, Present & Future

13:45 Vladimir Kolmogorov. University College London, UK

Scalable optimization techniques for certain graphical models

14:30 coffee 15:15 Daniel Marx. Tel Aviv University, Israel

Fixed-Parameter Algorithms

16:00 Lakhdar Sais. CRIL Lens, France

Structure-based simplification techniques of Boolean formulas

16:45 PhD Student session

17:15 reception 19:30 dinner at Queen’s College – invited speakers only

Tuesday, July 6

08:30 coffee 09:00 Andreas Krause. California Institute of Technology, U.S.A.

Submodular Optimization in Machine Learning and AI

09:45 Nikolaj Bjorner. Microsoft Research, U.S.A.

Engineering Satisfiability Modulo Theories solvers for intractable problems

10:30 coffee 11:00 Jakob Nordstrom. MIT and KTH , Sweden

Understanding Space in Proof Complexity

11:45 Tony Jebara. Columbia University, U.S.A.

Graphical Modeling and Machine Learning with Perfect Graphs

12:30 lunch 13:15 Paul Vitanyi. CWI & Universiteit van Amsterdam

Introduction to Kolmogorov complexity and applications

14:15 Miki Hermann. Ecole Polytechnique, France

What Makes Minimal Inference Tractable

15:00 Nadia Creignou. LIF Marseille, France

Phase transition for the satisfiability of random (quantified) Boolean formulas

15:45 Panel and Discussions 17:30 end of the workshop

PhD Session Thomas Windheuser

U. of Munich, Germany Interactive Image Segmentation Valentin Weber

G-SCOP lab, Grenoble, France Instances hardness and hard instances for NP-hard problems. Dhruv Batra

CMU . USA MAP Inference in Markov Random Fields via Outer-Planar Decomposition Caterina Vitadello

U. of Munich, Germany Human Motion Capture Robert Woodward

U. of Nebraska-Lincoln, USA Integrating Higher-Levels of Consistency in Solvers to Uncover Tractability of CSPs Danny Tarlow

U. Of Toronto, Canada Efficient message passing in certain high order models