International Workshop on Tractability; 5-6 July 2010

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

• Speaker to be confirmed
• Tuesday 06 July 2010, 09:00-17:30
• Lecture-room large(126 seats) Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), CB3 0FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

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

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

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Lecture-room large(126 seats) Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), CB3 0FB
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.