Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Vladimir V. Podolskii, Alexander A. Sherstov

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f:(\{0,1{\}}^n{)}^k\to \{0,1\}$ with $k\gg \log n$ parties. We…