Information Complexity is Computable
summary
Proves zero‑error information complexity is algorithmically approximable: given f on n×m and distribution μ produce a δ‑approximation by restricting to protocols with explicitly bounded rounds w (roughly at most (n/ε)^{O(n)}), then enumerating protocol trees for f^k to estimate amortized cost. Key tools are discretizing message functions into a finite signal net, reducing signals to uniform weak ones and bundling into boxes to limit interaction, plus Markov tail bounds; runtime is enormous but finite (double/triple‑exponential).
AI-written summary · about