Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-028 | 19th February 2024 09:57

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

RSS-Feed




TR24-028
Authors: Ashish Dwivedi, Zeyu Guo, Ben Lee Volk
Publication: 19th February 2024 18:31
Downloads: 160
Keywords: 


Abstract:

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC 2005) and Derksen and Viola's (FOCS 2022) had either suboptimal seed length or required the field size to depend on $n$.

Our approach follows Bogdanov's paradigm while incorporating techniques from Lecerf's factorization algorithm (J. Symb. Comput. 2007) and insights from the construction of Derksen and Viola regarding the role of indecomposability of polynomials.



ISSN 1433-8092 | Imprint