OpenAlex ·
Tight Lower Bounds for Algebraic Communication and Applications
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.17082
- Original
- Read it at the publisher
- Topics
Abstract
Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more 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. 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 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 give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems. We also prove reductions between different problems. 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. In a number of cases, these lower bounds match the corresponding upper bounds, giving tight or near-tight characterizations of their algebraic communication. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
On testing the incentive compatibility of single-parameter allocation mechanisms
Hidden Circuits and Exact Counting in Ordered Graphs
Structural Parameterizations for Eternal Vertex Cover
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.