Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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