How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games

DOI10.1109/FOCS.2011.78MaRDI QIDQ5494983zbMATH OpenFDO

Authors Alexandra Kolla, Konstantin Makarychev, Yury Makarychev

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.78

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Other game-theoretic models (91A40)

Cited in

(8)

• The simultaneous semi-random model for TSP
• Approximation Algorithms for CSPs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• The simultaneous semi-random model for TSP
• Planted models for the densest k-subgraph problem
• Exact recovery of planted cliques in semi-random graphs
• Independent sets in semi-random hypergraphs

This page was built for publication: How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494983)