BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Talks.cam//talks.cam.ac.uk// X-WR-CALNAME:Talks.cam BEGIN:VEVENT SUMMARY:International Workshop on Tractability\; 5-6 July 2010 - Speaker t o be confirmed DTSTART:20100706T080000Z DTEND:20100706T163000Z UID:TALK25449@talks.cam.ac.uk CONTACT:Microsoft Research Cambridge Talks Admins DESCRIPTION: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 di scuss their viewpoints on the question: What makes some difficult (that is \, NP-hard) problems tractable in practice?\n\n\nGoal of the Workshop \nTr actability has been studied under many different angles\, by different res earch communities and using a wide range of techniques. The workshop will provide a place for interactions between experts from those diverse backgr ounds\, including both theoreticians and practitioners. Topics explored du ring this workshop include:\n\nProof complexity \nGraphical properties \nL inear Relaxations \nReal-life versus random problems\, instance complexity \nSub-modularity and convexity \nTractable approximations \nFixed-paramet er tractability \nHybridization of techniques \nTractability in knowledge representation \nAlgebraic approaches to tractability \n\nWorkshop on Trac tability / Programme\nMonday\, July 5\n\n09:00 registration and coffee \n 09:50 welcome \n10:00 \n\nJohn Hooker. Carnegie Mellon University\, U.S. A\n\nIntegrating Solution Methods through Duality \n \n10:45 Peter Jeavons . University of Oxford\, UK\n\nPresenting Constraints\n \n11:30 \nGeorg Go ttlob. University of Oxford\, UK\n\nHypertree Decompositions \n \n12:15 lu nch \n13:00 \nJoao Marques-Silva. University College Dublin\, Ireland \n \nBoolean Satisfiability Solving: Past\, Present & Future \n \n13:45 \nVla dimir Kolmogorov. University College London\, UK \n\nScalable optimizatio n techniques for certain graphical models\n \n14:30 coffee \n15:15 Daniel Marx. Tel Aviv University\, Israel \n\nFixed-Parameter Algorithms\n \n16: 00 Lakhdar Sais. CRIL Lens\, France\n\nStructure-based simplification tec hniques of Boolean formulas\n \n16:45 PhD Student session\n \n17:15 recept ion \n19:30 dinner at Queen's College - invited speakers only \n\n\nTues day\, July 6\n\n08:30 coffee \n09:00 Andreas Krause. California Institut e of Technology\, U.S.A.\n\nSubmodular Optimization in Machine Learning an d AI \n \n09:45 Nikolaj Bjorner. Microsoft Research\, U.S.A.\n\nEngineerin g Satisfiability Modulo Theories solvers for intractable problems \n \n10: 30 coffee \n11:00 Jakob Nordstrom. MIT and KTH\, Sweden \n\nUnderstanding Space in Proof Complexity \n \n11:45 Tony Jebara. Columbia University\, U .S.A.\n\nGraphical Modeling and Machine Learning with Perfect Graphs \n \n 12:30 lunch \n13:15 Paul Vitanyi. CWI & Universiteit van Amsterdam\n\nIn troduction to Kolmogorov complexity and applications\n \n14:15 Miki Herman n. Ecole Polytechnique\, France\n\nWhat Makes Minimal Inference Tractable \n \n15:00 Nadia Creignou. LIF Marseille\, France\n\nPhase transition for the satisfiability of random (quantified) Boolean formulas \n \n15:45 Pane l and Discussions \n17:30 end of the workshop \n\n\n \nPhD Session \nThom as Windheuser \n\nU. of Munich\, Germany\n Interactive Image Segmentation \nValentin Weber \n\nG-SCOP lab\, Grenoble\, France\n Instances hardness and hard instances for NP-hard problems. \nDhruv Batra \n\nCMU. USA\n MAP Inference in Markov Random Fields via Outer-Planar Decomposition \nCater ina Vitadello \n\nU. of Munich\, Germany\n Human Motion Capture \nRobert Woodward\n\nU. of Nebraska-Lincoln\, USA \n Integrating Higher-Levels of C onsistency in Solvers to Uncover Tractability of CSPs \nDanny Tarlow\n\nU . Of Toronto\, Canada \n Efficient message passing in certain high order m odels \n\n LOCATION:Lecture-room large(126 seats) Microsoft Research Ltd\, 7 J J Thom son Avenue (Off Madingley Road)\, CB3 0FB END:VEVENT END:VCALENDAR