2026-07-23T03:28:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21037 2024-09-16T06:02:39Z ddc:004 open_access

Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields Dwivedi, Ashish Guo, Zeyu Volk, Ben Lee Pseudorandom Generators Low Degree Polynomials We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field 𝔽_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashish Dwivedi and Zeyu Guo and Ben Lee Volk 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.44 urn:nbn:de:0030-drops-210370 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.44 eng https://creativecommons.org/licenses/by/4.0/legalcode