International Workshop on Tractability; 5-6 July 2010

Add to your list(s) Download to your calendar using vCal

• Microsoft Research Events
• Monday 05 July 2010, 09:00-17:30
• Lecture-room large (126 seats) Microsoft Research Ltd, Roger Needham Building, 7 J J Thomson Avenue (Off Madingley Road), CB3 0FB.

If you have a question about this talk, please contact Speaker to be confirmed.

This talk has been canceled/deleted

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 [tentative schedule]

Nikolaj Bjorner

Microsoft Research, U.S.A. Engineering Satisfiability Modulo Theories

solvers for intractable problems

Nadia Creignou

LIF Marseille, France Phase transition for the satisfiability of

random (quantified) Boolean formulas

Georg Gottlob

University of Oxford, UK Hypertree Decompositions Miki Hermann

Ecole Polytechnique, France What Makes Minimal Inference Tractable John Hooker

Carnegie Mellon University, U.S.A. Integrating Solution Methods through Duality Peter Jeavons

University of Oxford, UK Presenting Constraints

Tony Jebara

Columbia University, U.S.A. Graphical Modeling and Machine Learning

with Perfect Graphs

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

Joao Marques-Silva

University College Dublin, Ireland Boolean Satisfiability Solving:

Past, Present & Future

Dániel Marx

Tel Aviv University, Israel Fixed-Parameter Algorithms

Jakob Nordström

MIT and KTH , Sweden Understanding Space in Proof Complexity Lakhdar Sais

CRIL Lens, France Structure-based simplification techniques

of Boolean formulas

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: Rachael Billing, msrcevnt@microsoft.com with following information:

Full name Company or University Country of Residence e-mail address

REGISTRATION DEADLINE 28TH JUNE 2010

This talk is part of the Microsoft Research Cambridge, general interest public talks series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.