Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols

Abstract

The polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times. As observed in [Alman and Williams, STOC 2017], almost all applications of the polynomial method in algorithm design ultimately rely on certain low-rank decompositions of the computation matrices corresponding to key subroutines. They suggest that making use of low-rank decompositions directly could lead to more powerful algorithms, as the polynomial method is just one way to derive such a decomposition. Inspired by their observation, in this paper, we study another way of systematically constructing low-rank decompositions of matrices which could be used by algorithms. It is known that various types of communication protocols lead to certain low-rank decompositions (e.g., \(\mathsf{P}\) protocols/rank, \(\mathsf{BQP}\) protocols/approximate rank). These are usually interpreted as approaches for proving communication lower bounds, while in this work we explore the other direction. We have the two generic algorithmic applications of communication protocols. The first connection is that a fast \(\mathsf{BQP}\) communication protocol for a function \(f\) implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. The second connection is that a fast \(\mathsf{AM}^{\mathsf{cc}}\) protocol for a function \(f\) implies a faster-than-bruteforce algorithm for \(f\textsf{-Satisfying-Pair}\). We also apply our second connection to shed some light on long-standing open problems in communication complexity. We show that if the Longest Common Subsequence problem admits an efficient \(\mathsf{AM}^{\mathsf{cc}}\) protocol, then polynomial-size Formula-\(\textsf{SAT}\) admits a \(2^{n - n^{1-\delta}}\) time algorithm for any constant \(\delta > 0\).