Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-217 | 28th September 2026 08:14

Hitting Sets for Polynomials with Small Partial Derivative Spaces

RSS-Feed




TR26-217
Authors: Shubham Bhardwaj, Ramprasad Saptharishi
Publication: 28th September 2026 10:39
Downloads: 55
Keywords: 


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.



ISSN 1433-8092 | Imprint