Pseudorandom Bits for Polynomials

Andrej Bogdanov, Emanuele Viola

Type: Article

Publication Date: 2010-01-01

Citations: 82

DOI: https://doi.org/10.1137/070712109

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields	2024	Ashish Dwivedi Zeyu Guo Ben Lee Volk
+ PDF Chat	Pseudorandom Generators for Polynomial Threshold Functions	2013	Raghu Meka David Zuckerman
+	A PRG for boolean PTF of degree 2 with seed length subpolynomial in ϵ and logarithmic in n	2018	Daniel M. Kane Sankeerth Rao
+ PDF Chat	New Pseudorandom Generators and Correlation Bounds Using Extractors	2025	Vinayak M. Kumar
+ PDF Chat	Pseudorandom generators for polynomial threshold functions	2010	Raghu Meka David Zuckerman
+	Pseudorandom Generators for Polynomial Threshold Functions	2009	Raghu Meka David Zuckerman
+	Pseudorandom Generators for Polynomial Threshold Functions	2009	Raghu Meka David Zuckerman
+	Fractional Pseudorandom Generators from the $k$th Fourier Level.	2020	Eshan Chattopadhyay Jason Gaitonde Abhishek Shetty
+	Fractional Pseudorandom Generators from the $k$th Fourier Level	2020	Eshan Chattopadhyay Jason Gaitonde Abhishek Shetty
+	Fourier growth of structured $\mathbb{F}_2$-polynomials and applications	2021	Jarosław Błasiok Peter Ivanov Yaonan Jin Chin Ho Lee Rocco A. Servedio Emanuele Viola
+	Fourier growth of structured $\mathbb{F}_2$-polynomials and applications	2021	Jarosław Błasiok Peter Ivanov Yaonan Jin Chin Ho Lee Rocco A. Servedio Emanuele Viola
+	Algebraic methods in randomness and pseudorandomness	2010	Madhu Sudan Swastik Kopparty
+	Pseudorandom Generators for Width-3 Branching Programs	2018	Raghu Meka Omer Reingold Avishay Tal
+	Pseudorandom Generators for Width-3 Branching Programs	2018	Raghu Meka Omer Reingold Avishay Tal
+	Fourier growth of structured $\mathbb{F}_2$-polynomials and applications	2021	Jarosław Błasiok Ivanov Pa Yaonan Jin Chin Ho Lee Rocco A. Servedio Emanuele Viola
+ PDF Chat	Pseudorandomness via the Discrete Fourier Transform	2018	Parikshit Gopalan Daniel M. Kane Raghu Meka
+	Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions.	2011	Benny Applebaum
+	Pseudorandomness and F<sub>2</sub>-Polynomials	2014	Ryan O’Donnell
+	Worst Case to Average Case Reductions for Polynomials	2008	Tali Kaufman Shachar Lovett
+	Fooling intersections of low-weight halfspaces	2017	Rocco A. Servedio Li-Yang Tan

Works That Cite This (36)

Action	Title	Year	Authors
+ PDF Chat	None	2017	Chin Ho Lee Emanuele Viola
+	Partition Rank and Analytic Rank are Uniformly Equivalent.	2021	Alex Cohen Guy Moshkovitz
+ PDF Chat	Partition and analytic rank are equivalent over large fields	2023	Alex Cohen Guy Moshkovitz
+	Gowers norm, function limits, and parameter estimation	2016	Yuichi Yoshida
+ PDF Chat	The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic	2011	Terence Tao Tamar Ziegler
+	Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem	2013	Sixia Chen Cristopher Moore Alexander Russell
+ PDF Chat	None	2011	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+ PDF Chat	Gowers Norm, Function Limits, and Parameter Estimation	2015	Yuichi Yoshida
+ PDF Chat	Quadratic Goldreich-Levin Theorems	2011	Madhur Tulsiani Julia Wolf
+	Small-Bias Sets for Nonabelian Groups	2013	Sixia Chen Cristopher Moore Alexander Russell

Works Cited by This (9)

Action	Title	Year	Authors
+	New correlation bounds for GF(2) polynomials using Gowers uniformity	2006	Emanuele Viola
+ PDF Chat	AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM	2008	Ben Green Terence Tao
+ PDF Chat	MODp-tests, almost independence and small probability spaces	2000	Claudia Bertram‐Kretzberg Hanno Lefmann
+ PDF Chat	Simple Constructions of Almost k‐wise Independent Random Variables	1992	Noga Alon Oded Goldreich Johan Håstad René Peralta
+	A new proof of Szemerédi's theorem	2001	W. T. Gowers
+	A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four	1998	W. T. Gowers
+	An inverse theorem for the Gowers U^3 norm	2005	Ben Green Terence Tao
+ PDF Chat	Gowers uniformity, influence of variables, and PCPs	2006	Alex Samorodnitsky Luca Trevisan
+ PDF Chat	Low-degree tests at large distances	2007	Alex Samorodnitsky