Infinite Communication Complexity and KW Games
Abstract
We characterize the Borel sets with an infinite version of Karchmer and Wigderson's game linking finite circuit complexity to communication complexity. To this end, we formulate an infinite version of communication complexity and prove that a given subset of the Cantor space is Borel if and only if a certain infinite communication game is solvable. We utilize this connection to provide new elementary and purely combinatorial proofs of some classical results in descriptive set theory, including the analytic separation theorem and the equivalence of monotone and positive Borel sets. Another consequence is a characterization of Borel separability via the winner of a certain "cut-and-choose" game, which we use to obtain new combinatorial proofs that neither the set of ill-founded trees nor any infinite parity function is Borel.
Related
- Infinite Subtraction Games with Periodic Outcomes and Aperiodic SG Values
- Multidimensional Infinite-Horizon Markovian Backward Stochastic Differential Equations with Continuous Coefficients and Nonzero-Sum Differential Games
- A Riccati Approach to Mixed H2/H∞ Closed-Loop Games for Infinite-Dimensional Stochastic Systems
- Infinite-Horizon Stochastic Recursive Differential Games with Jumps: Nonautonomous Coefficients and Nonzero Terminal Values
- The Computational Complexity of the Ungar Games on Distributive Lattices
BibTeX
@misc{leach2026infinite,
title = {{Infinite Communication Complexity and KW Games}},
author = {Evan Leach},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00633},
eprint = {2609.00633},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00633},
}
RIS
TY - UNPB
TI - Infinite Communication Complexity and KW Games
AU - Evan Leach
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00633
UR - https://arxiv.org/abs/2609.00633
AB - We characterize the Borel sets with an infinite version of Karchmer and Wigderson's game linking finite circuit complexity to communication complexity. To this end, we formulate an infinite version of communication complexity and prove that a given subset of the Cantor space is Borel if and only if a certain infinite communication game is solvable. We utilize this connection to provide new elementary and purely combinatorial proofs of some classical results in descriptive set theory, including the analytic separation theorem and the equivalence of monotone and positive Borel sets. Another consequence is a characterization of Borel separability via the winner of a certain "cut-and-choose" game, which we use to obtain new combinatorial proofs that neither the set of ill-founded trees nor any infinite parity function is Borel.
ER -