Hitting sets From Derivations: Waring Rank and Noncommutative ABPs

summary

The gist

We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r…

In short

The paper constructs an explicit polynomial-sized hitting set for polynomials whose partial derivative space is bounded by $r$ over a characteristic zero field. This result implies a poly(n, d,s)-sized hitting set for depth-3 powering circuits of size $s$ and degree $d$. The construction relies on a specific derivation and properties of its Wronskian to establish the hitting set.

Key concepts

Partial Derivative Space Dimension
This refers to the dimension of the space spanned by all possible partial derivatives of a polynomial. The paper shows that for certain polynomial classes, this space is bounded by $r$. This bound is crucial because it allows for the construction of a hitting set whose size depends polynomially on $n$, $d$, and this bound $r$.
Formal Derivation D
This is a specific differential operator defined as $D := Q(t) rac{d}{dt} + ext{terms involving } rac{ ext{bi}(t)}{1-it}$. It has the property that its kernel is the base field $F$, meaning it acts non-trivially on functions. This derivation is used to analyze the structure of polynomials related to the hitting set.
D-Wronskian
The D-Wronskian, denoted WD($g_1, ext{...}, g_r$), is a determinant constructed using a basis of partial derivatives ($g_i$) and the formal derivation $D$. If the derivation has a trivial field of constants, this Wronskian being non-zero guarantees that the chosen set of derivatives is linearly independent.
Depth-3 Powering Circuits
These circuits are a computational analogue to Waring rank. They involve expressing a polynomial as a sum of powers of linear forms, where the depth constraint limits how complex these expressions can be. The paper provides an explicit hitting set for this class, which is important for understanding the complexity of these circuits.

Terminology used across episodes

This episode discusses

The paper

Hitting sets From Derivations: Waring Rank and Noncommutative ABPs · Read on arXiv

Shubham Bhardwaj, Ramprasad Saptharishi

Tata Institute of Fundamental Research · Department of Atomic Energy, Government of India · Google · SERB Research Grants

We give an explicit hitting set of size poly(n,d,r) for the class of n-variate degree- d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero (or large enough). In particular, this yields a polynomial sized hitting set for the class of depth- 3 powering circuits. The proof extends to the setting of noncommutative ABPs and provides a polynomial sized hitting set (of matrices) for the class of noncommututive polynomials that can be computed by polynomial sized noncommutative ABPs (this was also one of the results reported by Open AI in their release on 6 Oct 2026). 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 in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: A subset of the stewards obtained a weaker statement (hitting sets for polynomials with bounded partial derivative space) during conversations with OpenAI GPT-6 Astra. Extensions of this idea to the broader class of noncommutative ABPs were obtained by the other stewards (via further conversations with Astra), prior to OpenAI's dump on 6 Oct 2026. The proofs presented in this writeup is a rewriting (in the authors' words) of the proofs for both settings obtained by the models in a form that we believe is understandable to researchers. Although the proof is technically identical to OpenAI's release, we believe this exposition is self-contained, simpler, and more valuable to the community. The absurdity of the situation is not lost on us.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Hitting sets From Derivations".

Jane: Here's the gist of the paper. We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero <ref:2609.34436#pg11>.

Tom: In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits <ref:2609.34436#pg12>.

Jane: The Core Result The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609.34436#pg13>.

Tom: Theorem 1.1 states that there is an explicit polynomial map (G1(t),..., Gn(t)) in F

t: n with deg Gi ≤ O(nr2) such that if f(x1,..., xn) is a polynomial such that dim ∂∗ f ≤ r, then f(x1,..., xn) = 0 ⇔ f(G1(t),..., Gn(t)) = 0 <ref:2609.34436#pg14>.

Title and authors: Tom: So Jane, this paper "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us a way to find these hitting sets for polynomials whose partial derivative space is small.

Jane: Right, so the main thing here is that they give us an explicit polynomial sized hitting set for any n-variate degree d polynomials where the partial derivative space is bounded by some number r, over any field with characteristic zero.

Lu: What's interesting about this specific result is that it shows this construction works even for a particular class called depth-three powering circuits, which the paper links directly to polynomial sized hitting sets <ref:2609.34436#pg1>.

Meng: I want to know what the practical implications are for something like training models at scale. If we can find these small hitting sets, does that mean we can effectively control or test these complex polynomial structures in a way that keeps things manageable?

Lalam: I'm looking at how they construct this hitting set, and it seems to rely on building a specific type of formal derivation and then using the properties of an associated Wronskian with respect to that derivation.

Tom: A Wronskian argument sounds complicated, but I see they are using this Wronskian to prove a final contradiction that shows the polynomial isn't zero modulo some number B.

Jane: So they use this derivation and the Wronskian to show that if the original polynomial is zero, then a certain related function has some property modulo B, but they show it doesn't because of how big B is compared to r and d.

Lu: The trick there seems to be relating the derivative of the composed function back to this formal derivation using a specific map defined by power series.

Meng: And this map they use is related to those power series we see in other works, like the one with ln(one minus it) <ref:2609.34436#pg1>. It seems like they are building a test that scales nicely with n, d, and r.

Lalam: The structure of this map is defined by Pi t equals negative log of one minus i t for each index i from one to n. This gives us a set of algebraically independent power series that are key to the construction.

Tom: Okay, so what's the actual improvement they suggest over previous work? I remember something about how this new approach simplifies things compared to older methods in circuit complexity.

Jane: They suggest an explicit hitting set construction based on this formal derivation, which is different from the randomized PIT algorithms they mention earlier, providing a deterministic path.

Lu: The paper notes that the proofs for this result are elementary and completely self-contained, which means you don't need to be an expert in those very specific contexts to follow the logic.

Meng: That’s helpful for production because it means we can actually trust the mechanics without needing a deep dive into specialized literature just to verify the construction itself.

Lalam: And they state that this explicit hitting set yields a poly(n, d,s) sized hitting set for depth-three powering circuits, which is what we were aiming for in terms of circuit analysis <ref:2609.34436#pg1>.

Tom: So the main takeaway is that by using this formal derivation and Wronskian argument, they get a concrete polynomial size hitting set for these polynomial classes.

Jane: It means we have a better tool to check if these complex polynomial structures are zero without having to evaluate them everywhere, relying instead on this specific transformation.

Lu: For the future work, the paper points toward how this relates to lower bounds and deterministic PITs, suggesting that strong circuit lower bounds can lead to efficient tests.

Meng: If we can use these hitting sets effectively for testing, it could mean we can build more robust methods for verifying model properties at scale, even when the underlying structure is complex.

Lalam: The paper also touches on how this relates to the idea that lower bounds and PITs are intimately connected, which is a big piece of context for anyone studying circuit complexity.

Tom: To wrap up, "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us an explicit way to find a polynomial sized hitting set for degree d polynomials with bounded partial derivative spaces.

Jane: It's a significant step because it provides an explicit construction using a formal derivation and Wronskian that connects the polynomial structure directly to this hitting set size bound.

Lu: And this method is elementary, which makes it much more accessible for researchers looking to apply these ideas in other areas of algebraic circuit analysis.

Meng: From an engineering standpoint, having a constructive proof like this means we have a reliable way to handle the complexity without relying on probabilistic methods that might not hold up in real deployment scenarios.

Lalam: The paper also connects this result to how lower bounds and deterministic polynomial identity tests are related, which is crucial context for understanding the connection between circuit size and test efficiency.

The paper's summary: Tom: So what we’re looking at here is this paper about finding explicit hitting sets for polynomials, specifically for these depth-three powering circuits where the partial derivative space is bounded by some number r over a field with no characteristic zero.

Jane: Right, so it seems they took this idea of a formal derivation and built a specific map—a transformation—that lets you check if that polynomial equals zero by just looking at something else.

Tom: Exactly. The big result is that they build an explicit hitting set for the class of size s, degree d depth-three powering circuits where the size s is bounded by something like n times r squared plus r cubed.

Lu: What I find really interesting is how they use this formal derivation and an associated Wronskian—which is a bunch of derivatives used to check independence—to show that if the original polynomial isn't zero, then a certain related function has some property modulo B.

Meng: So instead of just testing the whole massive polynomial, you’re looking at this derived function and seeing how it behaves with respect to this specific operator D.

Jane: And they prove that because of how big the number B is compared to n, d, and r, that function can't be zero modulo B unless the original polynomial actually was zero.

Tom: It’s a really neat contradiction based on the growth rates—the error term in their analysis doesn't let anything sneak through.

Jane: It means we get a concrete way to test these complex algebraic structures without having to search the entire space, which is something we always want when dealing with these massive polynomial expressions.

Lu: This method is completely self-contained; they don't rely on some huge external machinery, just their derivation and Wronskian properties.

Meng: That’s good for us because if it's explicit and elementary, we can actually try to use it to build a production system rather than just relying on theoretical guarantees.

Tom: So the main thing here is that we have this constructive tool—this polynomial sized hitting set—that works for these specific circuit classes, which is a big deal for understanding the limits of polynomial representation.

Jane: And this sets us up nicely because we’re going to talk next about how these kinds of explicit tests can actually be used to generate deterministic identity tests for polynomials where the partial derivative space is small.

The paper's improvements: Tom: So we just covered how they build an explicit hitting set for these depth-three powering circuits using this formal derivation and Wronskian argument over a field with no characteristic zero.

Jane: That was a lot of math, but essentially, they showed you can use this transformation to create a polynomial sized test for these complex structures.

Tom: Exactly. The improvement they’re highlighting is that this method is deterministic; it gives you a concrete construction instead of relying on some randomized tests or probabilistic guarantees.

Lu: What's really important here is the connection they draw between this hitting set size and lower bounds on certain circuit classes, which links polynomial testing to fundamental complexity questions.

Meng: For us in engineering, that’s huge because it means if we can prove a lower bound on how complex a model structure needs to be, this paper gives us a tool to actually check if it’s there efficiently.

Jane: They also point out that this framework is very general; the same idea works for any class of polynomials whose partial derivative space is bounded by some number r, over any field with no characteristic zero.

Tom: So the implication is that we don't need to worry about the specific structure of the polynomial as much as we do about how constrained its derivative space is.

Lu: They are also touching on how this relates to lower bounds and deterministic polynomial identity tests, suggesting that if you have a strong lower bound on a circuit, you can get an efficient test for it.

Meng: I’m interested in the practical application here; if we know something about the complexity of a model structure, this paper suggests we might be able to build tests that scale well with n and d.

Jane: It means that for someone just listening, the big idea is that these advanced mathematical tools can give us a reliable way to verify complicated polynomial relationships in a manageable time frame.

Tom: They’re essentially saying we have moved from maybe having some randomized identification tests to having an explicit, constructive way to find the right polynomials that are zero.

Lu: And this moves the needle on understanding how deep these circuit classes actually are, by providing a concrete method for checking their zero property.

Meng: It’s good because it’s not just theoretical; it’s about having a reliable mechanism to check things at scale, even if we don't know the absolute best complexity bounds yet.

Conclusion: Tom: So to wrap up, this paper "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us an explicit, polynomial sized hitting set for these depth-three powering circuits when the partial derivative space is bounded by some number r over a field with no characteristic zero.

Jane: It means we have a reliable construction, not just a theoretical idea, to check if these kinds of complex polynomials are actually zero without having to test every single point in the space.

Tom: Exactly. This explicit hitting set construction using the formal derivation and Wronskian argument is pretty clean for someone who wants to see how the mechanics work on paper.

Lu: I think it’s important because it ties these polynomial properties directly into lower bounds on circuit complexity, which is a big piece of context for where we are in this field.

Meng: For production, having an explicit construction means we can actually try to deploy tests based on these bounds, even if the size scales with n and r squared.

Lalam: I’m confident in this result because the proof is self-contained, and it connects directly to how we think about testing things at a fundamental level.

Jane: It's a significant step because it provides an explicit construction using a formal derivation and Wronskian that connects the polynomial structure directly to this hitting set size bound.

Tom: Yeah, so the main thing here is that we have moved from maybe having some randomized identification tests to having an explicit, constructive way to find the right polynomials that are zero.

Lu: This method is elementary, which makes it much more accessible for researchers looking to apply these ideas in other areas of algebraic circuit analysis.

Meng: From an engineering standpoint, having a constructive proof like this means we have a reliable way to handle the complexity without relying on probabilistic methods that might not hold up in real deployment scenarios.

Jane: And this sets us up nicely because we’re going to talk next about how these kinds of explicit tests can actually be used to generate deterministic identity tests for polynomials where the partial derivative space is small.

More episodes

← Home