July 5-6, 2010 - Microsoft Research, Cambridge
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
List of Invited Speakers
|
Microsoft Research, U.S.A. |
Engineering Satisfiability Modulo Theories solvers for intractable problems [slides] |
|
LIF Marseille, France |
Phase transition for the satisfiability of random (quantified) Boolean formulas [slides] |
|
University of Oxford, UK |
Hypertree Decompositions |
|
Ecole Polytechnique, France |
What Makes Minimal Inference Tractable [slides] |
|
Carnegie Mellon University, U.S.A. |
Integrating Solution Methods through Duality [slides] |
|
University of Oxford, UK |
Presenting Constraints [slides] |
|
Columbia University, U.S.A. |
Graphical Modeling and Machine Learning with Perfect Graphs [slides] |
|
University College London, UK |
Scalable optimization techniques for certain graphical models |
|
Caltech, U.S.A. |
Submodular Optimization in Machine Learning and AI [link] |
|
University College Dublin, Ireland |
Boolean Satisfiability Solving: Past, Present & Future [slides] |
|
Tel Aviv University, Israel |
Fixed-Parameter Algorithms [slides] |
|
MIT and KTH, Sweden |
Understanding Space in Proof Complexity [slides] |
|
CRIL Lens, France |
Structure-based simplification techniques of Boolean formulas [slides] |
|
CWI, Netherlands |
Introduction to Kolmogorov complexity and applications [slides] |
Participation
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
Organisers
- Lucas Bordeaux
- Youssef Hamadi
- Pushmeet Kohli
- Robert Mateescu
Location
Local Information
Workshop Contact
- Rachael Billing
Business & Events Coordinator
msrcevnt@microsoft.com
+44 (0) 1223 479 766
