COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Algorithmic Barriers from Phase Transitions

## Algorithmic Barriers from Phase TransitionsAdd to your list(s) Download to your calendar using vCal - Dimitris Achlioptas (University of Athens & RACTI)
- Tuesday 22 November 2011, 16:30-17:30
- MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact Elena Yudovina. This talk is cross-listed from the Probability series, because it should be of interest to this seminar as well. For many random optimization problems we have by now very sharp estimates of the satisfiable regime. At the same time, though, all known polynomial-time algorithms only find solutions in a very small fraction of that regime. We study this phenomenon by examining how the statistics of the geometry of the set of solutions evolve as constraints are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in that problem?s solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random optimization problems our results establish rigorously a substantial part of the 1-step Replica Symmetry Breaking picture of statistical physics for these problems. This talk is part of the Optimization and Incentives Seminar series. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Economics and Computer Science Talks
- MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- Optimization and Incentives Seminar
- School of Physical Sciences
- Statistical Laboratory info aggregator
Note that ex-directory lists are not shown. |
## Other listsMRC Epidemiology and CEDAR Seminars Martin Centre Research Seminars, Dept of Architecture Type the title of a new list here## Other talksTitle TBC G I TAYLOR LECTURE - Waves in the airways: a carpet of microscopic rowers keeps us alive C++ and the Standard Library A rose by any other name Formulations of community detection in terms of total variation and surface tension A sex-linked supergene controls sperm morphology and swimming speed in a songbird |