PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Lower Bounds for Algebraic Communication and Applications

Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan

arXiv:2609.17082v1cs.CC

TL;DR

The paper studies the communication complexity of polynomial evaluation and set recognition over R and C in a model where parties send polynomial evaluations of their separate inputs. The paper combines algebraic and analytic techniques to establish upper bounds, reductions, a general probabilistic lower-bound framework, and applications to algebraic scanners and BSS-inspired computation. The paper proves a tight 2n deterministic equality bound and shows probabilistic protocols have acceptance probability at most 1/3 when inputs differ.

  • Problem

    The paper studies the communication complexity of polynomial evaluation and set recognition over R and C in a model where parties send polynomial evaluations of their separate inputs.

  • Method

    The paper combines algebraic and analytic techniques to establish upper bounds, reductions, a general probabilistic lower-bound framework, and applications to algebraic scanners and BSS-inspired computation.

  • Results

    The paper proves a tight 2n deterministic equality bound and shows probabilistic protocols have acceptance probability at most 1/3 when inputs differ.

  • Takeaways & Limitations

    The results show that deterministic and probabilistic algebraic communication differ substantially and support lower bounds for broader algebraic algorithms and computational models.

  • Takeaways & Limitations

    The general framework does not apply to IPn because no u satisfies F(u)=0 and RF(u)≠0; the paper instead proves a 2n−4 lower bound by refining the proof.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies algebraic communication for polynomial evaluation and set recognition over R and C, extending classical communication complexity to polynomial messages and tests. It develops upper bounds, deterministic and probabilistic lower bounds, and applications to algebraic algorithms and BSS-inspired computation.

  • 1 Introduction: The model lets Alice and Bob communicate polynomial evaluations of their separate inputs to evaluate polynomials or recognize sets, in deterministic or probabilistic protocols.Set-recognition protocols use a referee whose polynomial tests determine acceptance or rejection.
  • 1 Introduction: A general framework proves probabilistic lower bounds for set-recognition problems, substantially generalizing prior techniques and quantitatively improving earlier bounds.The framework supports strong lower bounds whenever the relevant polynomial family satisfies specified conditions.
  • 1 Introduction: The lower-bound framework has two applications: lower bounds for left-to-right algebraic scanners and extensions to a broader BSS-inspired algebraic computational model.Algebraic scanners process inputs sequentially, store polynomial evaluations, and use polynomial tests to determine later actions.
  • 1 Introduction: The paper also provides non-trivial upper bounds and reductions across natural problems, organizing the model and showing algebraic communication can outperform sending all input coordinates.These results motivate the study of meaningful lower bounds in the model.
  • 1 Introduction: For polynomial evaluation, Abelson’s mixed Hessian gives a lower bound of twice its rank, yielding the tight bound 2n for the inner-product polynomial.For IPn, the mixed Hessian is the n × n identity matrix.
  • 1 Introduction: 2n is a tight deterministic communication bound for equality, whereas a probabilistic protocol recognizes equality with O(1) communication and error at most 1/3.The deterministic protocol sends all coordinates and checks equality coordinate by coordinate; the probabilistic protocol compares random polynomial encodings.

1.1 Our results and techniques

The paper develops upper bounds, reductions, and a general lower-bound framework for algebraic set-recognition, then applies these results to algebraic scanners and a BSS-inspired model.

  • Communication bounds and reductions: The paper also supplies non-trivial deterministic and probabilistic upper bounds and reductions among natural set-recognition problems.These results organize the model and show that algebraic communication can outperform sending every input coordinate.
  • Communication bounds and reductions: Probabilistic communication is O(1) for unordered equality and for sets differing in at most k coordinates when k=O(1).These problems therefore provide examples whose complexity can be much smaller than the full deterministic 2n bound.
  • Communication bounds and reductions: Deterministic equality has communication complexity exactly 2n over both R and C, and the proof does not assume homogeneous protocol polynomials.The upper bound sends all coordinates and tests coordinatewise equality; the matching lower bound adapts a classical fooling-set argument.
  • Framework for probabilistic communication: The lower-bound framework applies beyond inner product: irreducible polynomials satisfying the stated nondivisibility condition yield bounds when the relevant boundary intersection has dimension 2n−1.A refined analysis of the rank-to-communication connection improves the lifting parameters and broadens applicability.
  • New lower bounds: Probabilistic communication for thresholded or approximate equality is 2n over the relevant fields, while inner-product variants achieve lower bounds of at least 2n−4.For intersection variants, the closely related approximate sets have lower bound at least 2(n−3), improving earlier bounds for related problems.
  • Applications: Communication lower bounds transfer to lower bounds for left-to-right algebraic scanners and for a broader BSS-inspired algebraic computational model.The scanner applications include ℓ2-distance testing and detecting collisions between green and red points.

1.2 Related work

The paper situates its algebraic communication model among work on distributed algebraic computation, real communication, monotone circuits, secret sharing, and algebraic computation trees.

  • Prior work studies distributed algebraic computation, including polynomial-function communication when inputs are split between parties.
  • Related communication models allow arbitrary real or complex messages and direct party-to-party interaction rather than referee-mediated polynomial evaluations.
  • Other neighboring areas connect real communication with proof complexity, monotone circuits, and secret-sharing schemes.
  • The paper differs from Ben-Or’s algebraic computation-tree work in both its computational model and its lower-bound techniques.

1.3 Discussion and open problems

The discussion highlights unresolved tight bounds, broader applicability of the framework, and extensions to a different communication model.

  • The paper concludes its introduction with discussion and several open problems.
  • For S(IP_n) over R and V(IP_n) over C, the paper proves 2n −4 but leaves the tight 2n lower bound open.
  • The framework appears broadly applicable, but further natural set-recognition problems remain to be identified and analyzed.
  • Developing probabilistic lower-bound techniques for the distinct Bläser–Vicari communication model is another open direction.

2 Preliminaries

The preliminaries define algebraic polynomial-evaluation and set-recognition communication over R and C, together with deterministic and probabilistic protocols and foundational examples.

  • Polynomial evaluation communication lets Alice and Bob send one-party polynomial values, after which a referee applies a polynomial to compute g(X,Y).The cost is the total number of communicated values.
  • Polynomial-evaluation complexity c(g) is the minimum number of one-party polynomial values needed, and every polynomial has complexity at most 2n.
  • Set-recognition protocols use a tree of one-party message polynomials and referee tests whose outcomes determine the next branch and final acceptance.
  • The standard coordinate-wise equality protocol recognizes V(EQ_n) with cost 2n over both R and C.
  • Exact equality has a probabilistic protocol of cost 2, illustrating that probabilistic communication can be substantially cheaper than deterministic communication.

3 Communication bounds and reductions

This section develops communication bounds and reductions for equality, unordered equality, sparse difference, and bilinear forms, including tight deterministic and near-tight probabilistic results.

  • Equality: Under integer inputs, exact equality has deterministic complexity exactly 2 via an injective polynomial encoding of each party’s entire vector.
  • Reductions: Unordered equality reduces locally to ordinary equality by replacing each vector with its elementary symmetric polynomials.These polynomials determine the monic polynomial whose roots are the input coordinates, including multiplicities.
  • Equality: The deterministic complexity of exact equality V(X−Y) is exactly 2n over both R and C.The lower bound uses an open set of diagonal inputs following one accepting path and injectivity of each party’s transcript map.
  • Sparse difference: For sparse difference, equality reduces to the problem, yielding deterministic lower bounds, while a probabilistic protocol has cost 2k + 2 independent of n for fixed k.
  • Bilinear forms: Bilinear-form set-recognition complexities equal those of inner product at the matrix rank, transferring the corresponding lower bounds to real threshold and complex zero sets.The paper obtains a 2r −4 lower bound for both settings after establishing the inner-product bound.

4 Communication complexity via mixed Hessian rank

The mixed Hessian rank lower-bounds algebraic communication, yielding tight complexity bounds for polynomial evaluation, including inner product.

  • rank HX|Y(g) lower-bounds the communication complexity of computing g.
  • A minimum-size representation using Alice and Bob’s univariate messages has rank HX|Y(g) at most min{r1, r2}.
  • The rank framework gives tight bounds for the inner product polynomial, with communication complexity exactly 2n.
  • For g = p^m h with irreducible p and p ∤ h, a nondivisible r × r mixed-Hessian minor yields rank HX|Y(g) at least r − 2.
  • Under the full-rank criterion, powers of irreducible polynomials have rank HX|Y(g) = n, including after squaring when m ≥ 1.

5 Framework for probabilistic lower bounds

The paper develops real and complex geometric frameworks that force protocol testing polynomials to contain a defining irreducible factor, producing probabilistic lower bounds.

  • The framework proves probabilistic lower bounds by combining boundary or Zariski-closure geometry with mixed-Hessian rank arguments.
  • 5.1 Over the real numbers: Over R, a full-dimensional boundary intersection forces some protocol testing polynomial to be divisible by the irreducible defining polynomial F.
  • 5.1 Over the real numbers: The real theorem’s dimension condition is essential: if dim(∂S ∩ V(F)) ≤ 2n − 2, the contradiction establishing divisibility no longer follows.
  • 5.1 Over the real numbers: With only an r × r nondivisible mixed-Hessian minor, the corresponding real lower bound weakens to PCCR(S) ≥ 2(r − 2).
  • 5.1 Over the real numbers: The real framework yields PCCR(S(F)) ≥ 2n for threshold sets F(X,Y) ≤ 0 when F has a point with F(u)=0 and RF(u) ≠ 0.
  • 5.2 Over the complex numbers: Over C, the analogous Zariski-closure framework gives PCCC(V(F)) ≥ 2n under the corresponding irreducibility and witness conditions.

6 New probabilistic lower bounds

The framework establishes strong probabilistic lower bounds for ε-equality, ε-hypercube, inner-product, and ε-SI problems over R and C.

  • 6.1 The ε-equality set: The ε-equality defining polynomial is irreducible over R and C, and its threshold and complex hypersurface attain matching deterministic depth 2n upper bounds.
  • 6.2 The ε-hypercube set: The ε-hypercube problem recognizes whether X − Y is close to a Boolean-hypercube vertex, with matching deterministic depth 2n protocols and lower bounds.
  • 6.3 Inner product: PCCR(S(IPn)) and PCCC(V(IPn)) are each at least 2(n − 2), improving Grigoriev’s 2(n − 3) bound.
  • 6.4 The ε-SI set: For the ε-SI set, probabilistic and deterministic complexities over R and C are at least 2(n − 3).

7 Applications of communication lower bounds

Communication lower bounds transfer to left-to-right algebraic scanners, yielding linear or stronger costs for distance, collision, GCD, and resultant problems.

  • An algebraic scanner reads inputs left to right, stores polynomial values, and branches through equality or order tests within bounded memory and query counts.
  • Any (ℓ, t)-probabilistic scanner for a concatenated set eS must satisfy ℓ + t ≥ r whenever PCCF(S) ≥ r.
  • Algebraic probabilistic scanners for ε-ℓ2-distance over R require cost at least 2n, while bichromatic collision requires cost Ω(n) over R and C.
  • Over C, algebraic probabilistic scanners for both GCD and Resultant require cost Ω(n).

8 Extension to bounded-time BSS machines

The paper extends its lower-bound framework to bounded-time BSS machines, where local computations and branching use rational functions and semialgebraic computation paths. Despite this added local computational power, the same framework yields a BSS-probabilistic lower bound of at least 2n under the theorem’s assumptions.

  • 8 Extension to bounded-time BSS machines: The generalized model replaces polynomial local computations and tests with bounded-time BSS machines, while preserving the communication protocol structure.Alice, Bob, and the referee may use bounded-time BSS machines for local computation, branching, and transcript testing.
  • 8 Extension to bounded-time BSS machines: The paper concludes that the same lower-bound framework survives the BSS generalization, suggesting no greater set-recognition power from stronger local computation in this setting.This conclusion is stated specifically for semialgebraic set-recognition.
  • 8 Extension to bounded-time BSS machines: A bounded-time BSS machine partitions R^n into semialgebraic computation-path regions, with a rational-function output on each region.The model uses arithmetic operations, sign tests, and single-valued outputs; bounded-time execution permits an equivalent finite computation tree.
  • 8 Extension to bounded-time BSS machines: The mixed Hessian rank bound extends from polynomial to rational computations: rank H_X|Y(g) ≤ min{r1, r2}, constraining representations through Alice’s and Bob’s messages.The extension assumes rational functions are defined on the relevant regions and uses formal derivatives where denominators are nonzero.
  • 8 Extension to bounded-time BSS machines: Under the theorem’s semialgebraic and irreducibility assumptions, every protocol recognizing S has BSS-probabilistic communication complexity at least 2n.The proof is presented as a lift of the earlier probabilistic lower-bound theorem.
  • 8 Extension to bounded-time BSS machines: The framework’s traces record outer protocol paths together with paths through communication and transcript-testing BSS machines, yielding finitely many rational branch conditions.Along each trace, communicated and tested quantities are rational functions, and bounded time ensures finitely many traces.

A Proof of the mixed Hessian rank bound

The proof bounds the mixed Hessian rank of a polynomial represented through separate Alice- and Bob-side functions. Applying the chain rule factors the mixed derivatives through the message Jacobians, yielding rank at most min{r1, r2}.

  • A Proof of the mixed Hessian rank bound: For g(X,Y)=Q(a1(X),...,ar1(X),b1(Y),...,br2(Y)), the mixed Hessian rank satisfies rank H_X|Y(g) ≤ min{r1, r2}.The rank is taken over F(X,Y), and the representation is assumed minimum-size.
  • A Proof of the mixed Hessian rank bound: The chain-rule calculation expresses the mixed Hessian using the Jacobian matrices J_X(a) and J_Y(b), so its rank is limited by the smaller message dimension.The argument uses the regularity of the polynomial functions to interchange partial derivatives.
  • A Proof of the mixed Hessian rank bound: Consequently, the total number of Alice and Bob functions satisfies r1+r2 ≥ 2 rank H_X|Y(g).This follows from r1+r2 ≥ 2 min(r1,r2) together with the mixed Hessian rank bound.
Loading 2609.17082v1…