Improved Rounding for Parallel Repeated Unique Games

DOI10.1007/978-3-642-15369-3_54MaRDI QIDQ3588447zbMATH OpenOpenAlexFDO

Authors David Steurer

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_54

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multistage and repeated games (91A20)

Recommendations

• Near-optimal algorithms for unique games
• Efficient parallel strategy improvement for parity games
• Approximation algorithms for unique games
• scientific article; zbMATH DE number 724209
• Parallel repetition in projection games and a concentration bound
• Faster algorithms for mean-payoff parity games
• The fixpoint-iteration algorithm for parity games
• Playing extensive form games in parallel
• Optimal strong parallel repetition for projection games on low threshold rank graphs

Cited in

(3)

• Parallel repetition of two-prover one-round games: an exposition
• Information value of two-prover games
• Product Rules in Semidefinite Programming

This page was built for publication: Improved Rounding for Parallel Repeated Unique Games

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