Random low degree polynomials are hard to approximate.

Ido Ben‐Eliezer, Rani Hod, Shachar Lovett

Type: Article

Publication Date: 2008-01-01

Citations: 2

Locations

Electronic colloquium on computational complexity - View

Similar Works

Action	Title	Year	Authors
+	Random Low Degree Polynomials are Hard to Approximate	2009	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+	Random low-degree polynomials are hard to approximate	2011	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+	The density of weights of Generalized Reed--Muller codes	2009	Shachar Lovett
+ PDF Chat	Low-Degree Factors of Random Polynomials	2018	Sean O’Rourke Philip Matchett Wood
+	The density of weights of Generalized Reed--Muller codes	2009	Shachar Lovett
+ PDF Chat	On the Bias of Reed--Muller Codes over Odd Prime Fields	2020	Paul Beame Shayan Oveis Gharan Yang Xin
+	Bias vs structure of polynomials in large fields, and applications in information theory	2015	Abhishek Bhowmick Shachar Lovett
+	On the Bias of Reed-Muller Codes over Odd Prime Fields	2018	Paul Beame Shayan Oveis Gharan Yang Xin
+ PDF Chat	Low-Degree Approximation of Random Polynomials	2021	Daouda Niang Diatta Antonio Lerario
+	Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes	2022	Siddharth Bhandari Prahladh Harsha Ramprasad Saptharishi Srikanth Srinivasan
+	A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions	2017	Daniel M. Kane
+ PDF Chat	Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes	2022	Siddharth Bhandari Prahladh Harsha Ramprasad Saptharishi Srikanth Srinivasan
+	Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory	2015	Abhishek Bhowmick Shachar Lovett
+	Worst Case to Average Case Reductions for Polynomials	2008	Tali Kaufman Shachar Lovett
+	Explicit lower bound for fooling polynomials by the sum of small-bias generators.	2009	Shachar Lovett Yoav Tzur
+	Efficient deterministic approximate counting for low degree polynomial threshold functions.	2013	Anindya De Rocco A. Servedio
+	Bias implies low rank for quartic polynomials	2019	Amichai Lampert
+	Algorithmic regularity for polynomials and applications	2013	Arnab Bhattacharyya Pooya Hatami Madhur Tulsiani
+	Low Degree Testing over the Reals	2022	Vipul Arora Arnab Bhattacharyya Noah Fleming Esty Kelman Yuichi Yoshida
+ PDF Chat	Small Sample Spaces Cannot Fool Low Degree Polynomials	2008	Noga Alon Ido Ben‐Eliezer Michael Krivelevich

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors