Worst Case to Average Case Reductions for Polynomials

Tali Kaufman, Shachar Lovett

Type: Article

Publication Date: 2008-10-01

Citations: 59

DOI: https://doi.org/10.1109/focs.2008.17

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Worst Case to Average Case Reductions for Polynomials	2008	Tali Kaufman Shachar Lovett
+	Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory	2015	Abhishek Bhowmick Shachar Lovett
+	Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory	2015	Abhishek Bhowmick Shachar Lovett
+	Bias vs structure of polynomials in large fields, and applications in information theory	2015	Abhishek Bhowmick Shachar Lovett
+	Random low-degree polynomials are hard to approximate	2011	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+ PDF Chat	Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields	2024	Ashish Dwivedi Zeyu Guo Ben Lee Volk
+	Random Low Degree Polynomials are Hard to Approximate	2009	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+	Random low degree polynomials are hard to approximate.	2008	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+	Bias implies low rank for quartic polynomials	2019	Amichai Lampert
+	Pseudorandom Bits for Polynomials	2010	Andrej Bogdanov Emanuele Viola
+	Algorithmic regularity for polynomials and applications	2015	Arnab Bhattacharyya Pooya Hatami Madhur Tulsiani
+ PDF Chat	On the heuristic of approximating polynomials over finite fields by random mappings	2015	Rodrigo S. V. Martins Daniel Panario
+ PDF Chat	Low-Degree Factors of Random Polynomials	2018	Sean O’Rourke Philip Matchett Wood
+	Fractional Pseudorandom Generators from the $k$th Fourier Level	2020	Eshan Chattopadhyay Jason Gaitonde Abhishek Shetty
+	Algorithmic regularity for polynomials and applications	2013	Arnab Bhattacharyya Pooya Hatami Madhur Tulsiani
+ PDF Chat	Algorithmic regularity for polynomials and applications	2014	Arnab Bhattacharyya Pooya Hatami Madhur Tulsiani
+	Fractional Pseudorandom Generators from the $k$th Fourier Level.	2020	Eshan Chattopadhyay Jason Gaitonde Abhishek Shetty
+ PDF Chat	A Note on Random Polynomials	1970	Richard G. Wood
+	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

Works That Cite This (48)

Action	Title	Year	Authors
+ PDF Chat	Finite Field Models in Arithmetic Combinatorics – Twenty Years On	2024	Sarah Peluse
+	Zeroes of polynomials in many variables with prime inputs	2015	Stanley Yao Xiao Shuntaro Yamagishi
+	Structure vs. Randomness for Bilinear Maps	2021	Alex Cohen Guy Moshkovitz
+	Partition Rank and Analytic Rank are Uniformly Equivalent.	2021	Alex Cohen Guy Moshkovitz
+ PDF Chat	Structure vs. Randomness for Bilinear Maps	2022	Guy Moshkovitz Alex Cohen
+ 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
+	General systems of linear forms: Equidistribution and true complexity	2016	Hamed Hatami Pooya Hatami Shachar Lovett
+ PDF Chat	Diophantine equations in the primes	2014	Brian Cook Ákos Magyar
+ PDF Chat	Higher-order Fourier Analysis and Applications	2019	Hamed Hatami Pooya Hatami Shachar Lovett

Works Cited by This (4)

Action	Title	Year	Authors
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2007	Ben Green Terence Tao
+ PDF Chat	Inverse conjecture for the gowers norm is false	2008	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+ PDF Chat	The Sum of D Small-Bias Generators Fools Polynomials of Degree D	2009	Emanuele Viola
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2009	Ben Joseph Green Terence Tao