Communication Complexity With a Prover: Applications to Fine-Grain Complexity

Abstract

While the field of fine-grain complexity has been around for fifteen years, recent work has opened up new directions. A 2017 paper introduced a method for proving hardness results in P based on communication protocols in the Merlin-Arthur setting and probabilistically checkable proofs. A follow-up paper expanded on these techniques and used them to prove results based on hardness assumptions about the satisfiability of branching programs. We continue this line of work, specifically proving that under the assumption that the satisfiability of branching programs of linear size cannot be checked substantially faster than in time 2^n, the orthogonal vectors problem cannot be solved substantially faster than in quadratic time.