  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$.
