International Workshop on Tractability

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


      Click [here] for the detailed programme and abstracts of all talks


List of Invited Speakers

Nikolaj Bjorner

Microsoft Research, U.S.A.

Engineering Satisfiability Modulo Theories

solvers for intractable problems [slides]

Nadia Creignou

LIF Marseille, France 

Phase transition for the satisfiability of

random (quantified) Boolean formulas [slides]

Georg Gottlob

University of Oxford, UK 

Hypertree Decompositions 

Miki Hermann

Ecole Polytechnique, France 

What Makes Minimal Inference Tractable [slides]

John Hooker

Carnegie Mellon University, U.S.A.

Integrating Solution Methods through Duality [slides]

Peter Jeavons

University of Oxford, UK

Presenting Constraints [slides]

Tony Jebara

Columbia University, U.S.A.

Graphical Modeling and Machine Learning

with Perfect Graphs [slides]

Vladimir Kolmogorov

University College London, UK 

Scalable optimization techniques

for certain graphical models

Andreas Krause

Caltech, U.S.A.

Submodular Optimization

in Machine Learning and AI [link]

Joao Marques-Silva

University College Dublin, Ireland 

Boolean Satisfiability Solving:

Past, Present & Future [slides]

Dániel Marx

Tel Aviv University, Israel 

Fixed-Parameter Algorithms [slides]

Jakob Nordström

MIT and KTH, Sweden 

Understanding Space in Proof Complexity [slides]

Lakhdar Sais

CRIL Lens, France 

Structure-based simplification techniques

of Boolean formulas [slides]

Paul Vitanyi

CWI, Netherlands

Introduction to Kolmogorov complexity

and applications [slides]



In addition to our invited speakers, participation is open to anyone interested to attend. Registration is nevertheless required. Your name will appear on a list of participants published on this web-page. To register, please send an e-mail to the Workshop contact and indicate:

  • Full name
  • Company or University
  • Country of Residence
  • e-mail address
  • Lucas Bordeaux
  • Youssef Hamadi
  • Pushmeet Kohli
  • Robert Mateescu
Local Information
Workshop Contact