A note on exact external information complexity
cs.CC
Submitted: 2026-11-08
Updated: 2026-11-08
Terminology
Sources
- New Separations Results for External Information
- Information complexity of the AND function in the two-Party, and multiparty settings
- Lower bounds on information complexity via zero-communication protocols and applications
- Trading information complexity for error II: the case of a large error and external information complexity
- The Infinite-message Limit of Two-terminal Interactive Source Coding
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?