New tight bounds reveal limits of algebraic communication tasks
Tight Lower Bounds for Algebraic Communication and Applications
Computational Complexity
Summary
This work studies how two people can share information efficiently when given parts of a problem expressed as numbers rather than simple yes/no answers. The authors look at how much communication it takes to evaluate polynomial functions or decide if certain conditions are met based on their separate inputs. They provide methods to prove the smallest amount of information that must be exchanged in different scenarios, and show how these results apply to certain algebra-based algorithms. Their framework deepens understanding of communication limits in mathematical computation tasks.
What this means in practice
- •For algorithm designers: Avoid inefficient algebraic communication protocols by relying on proven lower bounds to guide algorithm design for distributed polynomial computations.
- •For computational geometry teams: Use the lower bound framework to assess feasibility and communication costs of geometric set-recognition tasks split among multiple processors.
A theory result. No direct application yet.
Authors
Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan
Abstract
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 only 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 rejection. 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 evaluation 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.