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