Hitting sets simplify testing specific structured polynomials efficiently
Hitting Sets for Polynomials with Small Partial Derivative Spaces
Computational Complexity
Summary
The paper finds a way to efficiently test if certain complex math expressions, called polynomials, are zero without having to check every possible input. These polynomials have a special property that limits their complexity, defined by something called the partial derivative space. The authors create explicit sets of test inputs that are much smaller but still effective. This helps with understanding and working with certain circuit models in computer science. They also use an old mathematical tool called a Wronskian in a new way to make their proof simple and clear.
What this means in practice
- •For circuit designers: Check the correctness of specific algebraic circuits by testing fewer inputs for zero output due to bounded derivative complexity.
- •For software verification teams: Speed up testing of symbolic expressions with restricted partial derivative structures to detect bugs in computer algebra systems.
A theory result. No direct application yet.
Authors
Shubham Bhardwaj, Ramprasad Saptharishi
Abstract
We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The main technical insight is the construction of a "formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Moura_2004] in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: The proof of this result was obtained during conversations [astra_proof] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors' words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.