8 citations · 16 across the 15 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
cs.CC2024
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi +1
We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial computed by a constant-depth circuit over rational numbers, and outputs a…
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…