On the complexity of succinct zero-sum games
From MaRDI portal
Publication:1024660
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
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