An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication ComplexityResearch Paper
Communication complexity measures how many bits participants must exchange when each sees only part of an input. In the number-on-forehead model, there are participants and input blocks: participant sees every block except block . Their overlapping knowledge makes lower bounds difficult. A separation between randomness and nondeterminism asks whether…