NP-Hardness and Additive Inapproximability of Deterministic Communication ComplexityResearch Paper
Deterministic communication complexity asks how many bits two players must exchange to evaluate a Boolean function whose input is split between them. Yao introduced the model in 1979 (Yao, STOC 1979) and it has since become a basic tool for lower bounds on circuits, data structures, streaming algorithms and proof systems (Kushilevitz–Nisan, Communication…