On the complexity of succinct zero-sum games

DOI10.1007/s00037-008-0252-2zbMath1162.91302OpenAlexW2148042319MaRDI QIDQ1024660

Christopher Umans, Russell Impagliazzo, Valentine Kabanets, Lance J. Fortnow

Publication date: 17 June 2009

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0252-2

Mathematics Subject Classification ID

Computational learning theory (68Q32) 2-person games (91A05) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Weighted Boolean Formula Games ⋮ The landscape of communication complexity classes ⋮ Parallel approximation of min-max problems ⋮ Complexity limitations on one-turn quantum refereed games ⋮ On the Complexity of Equilibria Problems in Angel-Daemon Games ⋮ Arthur and Merlin as oracles ⋮ The 1-versus-2 queries problem revisited ⋮ On zero error algorithms having oracle access to one query ⋮ Arthur and Merlin as Oracles ⋮ The Complexity of the Nucleolus in Compact Games ⋮ The complexity of estimating min-entropy