The space complexity of mirror games

DOI10.4230/LIPICS.ITCS.2019.36MaRDI QIDQ5090413zbMATH OpenFDO

Authors Sumegha Garg, Jon Schneider

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1710.02898

zbMATH Keywords

eventown-oddtownmirror gamesspace complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The set coincidence game: Complexity, attainability, and symmetric strategies
• Variations on a game of Gale. II: Markov strategies
• The Big Match in small space (extended abstract)
• Bounding memory for Mastermind might not make it harder
• Parallel Repetition of the Odd Cycle Game

Cites work

• 3-query locally decodable codes of subexponential length
• Computational Complexity
• Data streams: algorithms and applications.
• scientific article; zbMATH DE number 1889828 (Why is no real title available?)
• Intersection theorems with geometric consequences
• Matching vector codes
• New bounds for matching vector families
• On Subsets with Intersections of Even Cardinality
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs

Cited in

(2)

• Mirror games against an open book player
• Finding missing items requires strong forms of randomness

This page was built for publication: The space complexity of mirror games

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