4 papers
cs.CC2025
Debordering Closure Results in Determinantal and Pfaffian Ideals
Anakin Dey, Zeyu Guo
One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied t…
cs.CC2025
Deterministic Depth-4 PIT and Normalization
Zeyu Guo, Siki Wang
In this paper, we initiate the study of deterministic PIT for circuits over fields of any characteristic, where and are bounded. Our main result is a det…
cs.CC2024
Hilbert Functions and Low-Degree Randomness Extractors
Alexander Golovnev, Zeyu Guo, Pooya Hatami +2
For , consider the linear space of restrictions of degree- polynomials to . The Hilbert function of , denoted , is the…
cs.CC2024
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
Ashish Dwivedi, Zeyu Guo, Ben Lee Volk
We construct explicit pseudorandom generators that fool -variate polynomials of degree at most over a finite field . The seed length of our generators is $O(d…