|
Computer Science Seminar Date: Thursday, 3 October 2024 Time: 8.30 PM - 9.30 PM Venue: Online mode Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields Zeyu Guo The Ohio State University. 03-10-24 Abstract We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field Fq. 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. Joint work with Ashish Dwivedi and Ben Lee Volk. Speaker's bio: Zeyu is an Assistant Professor in the Department of Computer Science and Engineering at the Ohio State University. He received his Ph.D. (guided by Chris Umans) in Computer Science from the California Institute of Technology in 2017. Before joining OSU, he did his postdocs at the University of Texas at Austin, the University of Haifa in Israel, and the Indian Institute of Technology Kanpur in India. He works in theoretical computer science. His research interests include computational complexity, pseudorandomness, coding theory, algebraic complexity theory, algebraic algorithms, and applications of algebraic methods in theoretical computer science in general.
|
