Abstract
In recent years, the polynomial method from circuit complexity has been applied to several fundamental problems and obtains the stateoftheart running times (e.g., R. Williams's n^3 / 2^{Omega(sqrt{log n})} time algorithm for APSP). As observed in [Alman and Williams, STOC 2017], almost all applications of the polynomial method in algorithm design ultimately rely on certain (probabilistic) lowrank decompositions of the computation matrices corresponding to key subroutines. They suggest that making use of lowrank 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 lowrank decompositions of matrices which could be used by algorithms  communication protocols. Since their introduction, it is known that various types of communication protocols lead to certain lowrank decompositions (e.g., P protocols/rank, 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 following two generic algorithmic applications of communication protocols:
 Quantum Communication Protocols and Deterministic Approximate Counting. Our first connection is that a fast BQP communication protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP communication protocols, we get fast deterministic additive approximate counting algorithms for CountOV (#OV), Sparse CountOV and Formula of SYM circuits. In particular, our approximate counting algorithm for #OV runs in nearlinear time for all dimensions d = o(log^2 n). Previously, even no trulysubquadratic time algorithm was known for d = omega(log n).
 ArthurMerlin Communication Protocols and Faster SatisfyingPair Algorithms. Our second connection is that a fast AM^{cc} protocol for a function f implies a fasterthanbruteforce algorithm for fSatisfyingPair. Using the classical GoldwasserSisper AM protocols for approximating set size, we obtain a new algorithm for approximate MaxIP_{n,c log n} in time n^{2  1/O(log c)}, matching the stateoftheart algorithms in [Chen, CCC 2018].
We also apply our second connection to shed some light on longstanding open problems in communication complexity. We show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) AM^{cc} protocol (polylog(n) complexity), then polynomialsize FormulaSAT admits a 2^{n  n^{1delta}} time algorithm for any constant delta > 0, which is conjectured to be unlikely by a recent work [Abboud and Bringmann, ICALP 2018]. The same holds even for a fast (computationally efficient) PH^{cc} protocol.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2018:10116,
author = {Lijie Chen and Ruosong Wang},
title = {{Classical Algorithms from Quantum and ArthurMerlin Communication Protocols}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {23:123:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10116},
URN = {urn:nbn:de:0030drops101162},
doi = {10.4230/LIPIcs.ITCS.2019.23},
annote = {Keywords: Quantum communication protocols, ArthurMerlin communication protocols, approximate counting, approximate rank}
}
Keywords: 

Quantum communication protocols, ArthurMerlin communication protocols, approximate counting, approximate rank 
Collection: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 