Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals

Markus Bläser, Christian EngelsSTACS 2011 · OpenReview

TL;DR

This paper introduces a new, highly efficient method for testing if a sparse polynomial (one with few terms) is identically zero, even when its degree is unknown. They achieve this by developing a "hitting set generator" that requires significantly fewer random bits and is independent of the polynomial's degree, a major improvement over prior work. This leads to faster randomized and deterministic algorithms for this fundamental problem in computer science.

What Problem Does This Paper Address?

Imagine you have a black box that can evaluate a polynomial, but you don't know its formula, only that it has a limited number of terms (it's "sparse"). The problem is to determine if this polynomial is always zero, no matter what values you plug in. This is called Polynomial Identity Testing (PIT). While easy if you have the formula, it's tricky with a black box.

A common approach is to use a "hitting set": a collection of points such that if a polynomial is not identically zero, at least one of these points will reveal it (i.e., the polynomial evaluates to a non-zero value at that point). The challenge is to find a small hitting set, especially when the polynomial's degree can be enormous. Previous methods often required random bits that grew with the degree, making them impractical for high-degree polynomials. This paper tackles the problem of creating efficient hitting sets and PIT algorithms for sparse polynomials over the real numbers, specifically aiming to make them independent of the polynomial's degree.

Methods

The core of the paper lies in constructing a "hitting set generator." Instead of generating a fixed hitting set, this generator takes a short random "seed" and produces a point that's likely to reveal a non-zero polynomial. The authors achieve this by:

  • Leveraging Sparse Polynomial Properties: They build upon ideas related to Descartes' Rule of Signs, which limits the number of positive real roots a sparse polynomial can have.
  • Randomized Monomial Substitution: A key technique is to transform a polynomial with many variables into one with fewer variables by replacing each original variable with a combination of new variables. This substitution is randomized, controlled by the seed.
  • Hitting Set Transformation: They develop a method to transform a hitting set for a simpler problem (e.g., polynomials with fewer variables) into a hitting set for a more complex one. This allows them to build up their solution from a basic case.
  • Deterministic Approach: For a deterministic test (no randomness), they combine their generator with a brute-force search over all possible seeds, leveraging the efficiency of their generator.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Degree Independence is Achievable: The most significant insight is that for sparse polynomials over the reals, it's possible to create hitting sets and testing algorithms whose efficiency (in terms of seed length and running time) is independent of the polynomial's degree. This was a major hurdle in prior work.
  • Randomness Efficiency: The paper demonstrates a substantial reduction in the number of random bits required for testing, making the randomized algorithms much more practical.
  • Bridging Theory and Practice: The work connects theoretical concepts like Descartes' Rule of Signs and algebraic geometry techniques to practical algorithmic improvements in polynomial identity testing.
  • Tradeoffs: The authors highlight a tradeoff between randomness and running time, allowing for flexibility depending on the specific constraints.

Key Results

  • Randomized Algorithm: A randomized algorithm for testing sparse black box polynomial identities over the reals is presented. It uses $O(\log^2(mn/\epsilon))$ random bits (where $m$ is the number of monomials, $n$ is the number of variables, and $1-\epsilon$ is the hitting probability) and runs in time polynomial in $\log m$, $n$, and $\log(1/\epsilon)$. This is a significant improvement in seed length, being independent of the degree.
  • Deterministic Algorithm: A deterministic algorithm is developed with a running time of $\tilde{O}(m^3 n^3)$ (where $\tilde{O}$ suppresses polylogarithmic factors). This is also independent of the degree, outperforming previous deterministic tests that depended polynomially on the degree.

Limitations and Future Work

  • Lower Bound Gap: While the paper achieves a seed length of $O(\log^2 mn)$, the theoretical lower bound for sparse polynomials is $(1-\epsilon)\log m$. Bridging this gap remains an open problem. The authors suggest that a more refined use of the Schwartz-Zippel generator might be a path forward.
  • Fields vs. Reals: The paper focuses on polynomials over the real numbers. The authors note that for arbitrary fields, dependence on the degree is generally necessary, as illustrated by a simple example involving finite fields. Extending these results to other fields or exploring the nuances of different field characteristics could be future work.
  • Practical Implementation: While theoretically efficient, the practical performance of these algorithms would depend on the constants hidden in the $\tilde{O}$ notation and the specific implementation details.

Summary updated

Abstract

We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree. From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon). We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.
BibTeX
@inproceedings{blaser2011randomness,
  author = {Markus Bläser and Christian Engels},
  title = {{Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals}},
  booktitle = {STACS},
  year = {2011},
  url = {https://openreview.net/forum?id=ZZe5uGe5pW},
}
Figure