Infinite Communication Complexity and KW Games
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.00633
curl -X POST /api/v1/records/arxiv/2609.00633/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.00633/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'