Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. The classical setting deals with Boolean inputs split between two parties. In this work, we study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$.
There are two players, Alice and Bob, with inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks. In the polynomial evaluation problem, the goal is to compute the value of a polynomial $g\in \mathbb{F}[X,Y]$ on the given input. In the set-recognition problem, the goal is to decide whether $(X,Y)\in S$, for a given set $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$. In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the polynomial evaluation problem, these messages are combined to compute the evaluation $F(X,Y)$. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic.
This algebraic communication viewpoint, initiated by Abelson (JACM, 1980) and later developed by Grigoriev (Computational Complexity, 2008), has remained comparatively unexplored. In this work, we revisit this model and demonstrate that it continues to offer a rich framework for new lower bound questions. We present three sets of results.
- Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems, showing that algebraic communication can be significantly more powerful than simply sending all input coordinates. We also prove reductions between different problems, which help organize the landscape of the model and identify which problems capture its main difficulties. These results serve two purposes: they illustrate the expressive power of the model, and they show that proving meaningful lower bounds in this setting is interesting.
- A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. Using this framework, we prove several probabilistic lower bounds for natural problems introduced earlier in the paper. In a number of cases, these lower bounds match the corresponding upper bounds, giving tight or near-tight characterizations of their algebraic communication.
Along the way, we also recover and generalize some of Grigoriev's original lower bound results.
- Applications of the framework: Finally, we give two applications of our framework. First, we use the communication lower bounds to prove lower bounds for a class of left-to-right algebraic algorithms, which we call algebraic scanners. Second, we show that our lower bound arguments extend beyond polynomials to a more general algebraic computational setting inspired by the Blum-Shub-Smale model.

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending nly on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or ejection. The protocols may be deterministic or probabilistic. We study:
- Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial valuation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model.
- A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication.
- Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.