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 > Isaac Newton Institute Seminar Series > How to Play Unique Games Against a Semi-Random Adversary

## How to Play Unique Games Against a Semi-Random AdversaryAdd to your list(s) Download to your calendar using vCal - Makarychev, K (IBM Research)
- Tuesday 24 May 2011, 14:00-15:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis We study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces (“corrupts’‘) the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1-delta)-fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is at least log k). Our result holds only for epsilon less than some absolute constant. We prove that if epsilon 1/2, then the problem is hard, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1-epsilon) satisfiable semi-random instance and (ii) the instance is at most delta satisfiable (for every delta > 0); the result assumes the 2-to-2 Unique Games conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an arbitrary (1-delta)-satisfiable instance (if epsilon > c delta, for some absolute constant c).
This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsType the title of a new list here sleg Sustainability in the Built Environment (GreenBRIDGE)## Other talksAspects of adaptive Galerkin FE for stochastic direct and inverse problems Mechanical properties of cells or cell components on the micro- and nanometer scale HE@Cam Seminar: Christian Hill - Patient Access Scheme, Managed Access Agreements and their influence on the approval trends on new medicines, devices and diagnostics Advanced NMR applications C++ and the Standard Library |