Sparsity Lower Bounds for Probabilistic Polynomials

Josh Alman, Arkadev Chattopadhyay, Ryan WilliamsITCS 2025 · OpenReview

TL;DR

This paper establishes fundamental limits on the "sparsity" (number of terms) of probabilistic polynomials used to represent Boolean functions. The authors prove that for certain crucial functions, like the AND of ORs, existing polynomial representations are already near-optimal in terms of sparsity, ruling out a common avenue for achieving breakthroughs in algorithms for problems like All-Pairs Shortest Paths (APSP) and the Strong Exponential Time Hypothesis (SETH).

What Problem Does This Paper Address?

In theoretical computer science, probabilistic polynomials are a powerful tool for designing efficient algorithms, particularly for problems like All-Pairs Shortest Paths (APSP) and Orthogonal Vectors (OV). The efficiency of these algorithms often hinges on the "sparsity" of the probabilistic polynomials used – essentially, how few terms (monomials) they contain. While significant progress has been made on lower bounds for the degree of these polynomials, understanding their sparsity has been a more challenging open problem. This paper aims to fill that gap by proving strong lower bounds on the sparsity of probabilistic polynomials for key Boolean functions, thereby understanding the limits of current algorithmic techniques and potentially refuting certain complexity conjectures.

Methods

The authors employ a combination of sophisticated techniques:

  • Random Restrictions: A core method involves applying random restrictions to the input variables of a probabilistic polynomial. This process is designed to significantly reduce the degree of the polynomial while carefully controlling the number of variables affected.
  • Schwartz-Zippel Lemma Variants: The paper leverages a version of the Schwartz-Zippel Lemma, which relates the degree of a polynomial to the probability of it evaluating to zero. This is crucial for proving lower bounds on sparsity.
  • Communication Complexity: Connections to communication complexity, particularly the number-on-forehead model, are used to derive lower bounds for certain circuit classes, which in turn inform polynomial sparsity bounds.
  • Algebraic Techniques: The proofs are generalized to hold over arbitrary commutative rings and for arbitrary "bases" (pairs of elements representing true and false), requiring careful algebraic manipulation.
  • Probabilistic Method: Techniques like the probabilistic method and union bounds are used to reason about the existence of polynomials with desired properties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Sparsity is a Hard Constraint: The paper demonstrates that for certain fundamental functions, achieving very low sparsity is inherently difficult, even with probabilistic polynomials. This suggests that algorithmic improvements relying on sparser polynomials might be blocked for these functions.
  • Tightness of Bounds: The authors show that their lower bounds are tight, meaning that constructions exist that achieve sparsity close to the proven lower bound. This confirms the optimality of existing approaches in a broad sense.
  • Basis Independence: A significant achievement is proving lower bounds that hold for any commutative ring and any choice of basis for representing "true" and "false." This makes the results more broadly applicable.
  • Separation of Sparsity and Rank: The paper explores the relationship between probabilistic sparsity and probabilistic rank, proving separations that highlight distinct limitations of these two related notions.
  • Implications for SETH/APSP: The results directly impact the quest to refute the Strong Exponential Time Hypothesis (SETH) and improve algorithms for All-Pairs Shortest Paths (APSP), by showing that a common algorithmic strategy is unlikely to yield the desired breakthroughs.

Key Results

  • AND of ORs: The AND of $n$ ORs of $c \log n$ variables requires probabilistic polynomials with sparsity $n^{\Omega(\log c)}$ over most commutative rings to achieve an error of $1/4$. This bound is tight.
  • Disjointness Function: The disjointness function on two $n$-bit vectors requires exponential sparsity for exponentially low error.
  • Degree-Sparsity Tradeoff: Any function requiring probabilistic polynomials of degree $d$ must require probabilistic polynomials of sparsity $\Omega(2^d)$.
  • Probabilistic Rank vs. Sparsity: The paper proves separations between probabilistic rank and probabilistic sparsity for various functions, showing that these two measures can differ significantly.
  • Basis Independence for AND: The AND function on $n$ variables has no probabilistic polynomial with $2^{o(n)}$ sparsity, $o(n)$ degree, and $1/2^{o(n)}$ error simultaneously, over any commutative ring and any basis $\{a,b\}$ for true/false.

Limitations and Future Work

  • Basis Independence for General Functions: While the paper proves basis independence for the AND function, extending this to more complex functions remains an open problem.
  • "Basis Independent" Lower Bounds: The authors leave open the problem of proving "basis independent" lower bounds where false can correspond to any value in the ring, not just 0.
  • Constructing Sparse Polynomials: New techniques for constructing sparse polynomial representations are called for, especially for specific circuit classes.
  • Probabilistic Rank for Specific Circuits: Investigating whether certain circuits, like the OR $\circ$ AND $\circ$ OR$_2$ circuit, have low probabilistic rank over some rings is an interesting future direction.

Summary updated

Abstract

Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds.
BibTeX
@inproceedings{alman2025sparsity,
  author = {Josh Alman and Arkadev Chattopadhyay and Ryan Williams},
  title = {{Sparsity Lower Bounds for Probabilistic Polynomials}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=5NPHVBvl2N},
}
Figure