Hard Functions for Low-Degree Polynomials over Prime Fields

Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka

Type: Article

Publication Date: 2013-07-01

Citations: 0

DOI: https://doi.org/10.1145/2493246.2493248

View Publication

Locations

ACM Transactions on Computation Theory - View

Similar Works

Action	Title	Year	Authors
+	Hard Functions for Low-Degree Polynomials over Prime Fields	2011	Andrej Bogdanov Akinori Kawachi Hidetoki Tanaka
+	Hard Functions for Low-degree Polynomials over Prime Fields (Extended Abstract)	2010	Bogdanov Andrej Akinori Kawachi Hidetoki Tanaka
+	Inverse Conjecture for the Gowers norm is false	2007	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+	Inverse Conjecture for the Gowers norm is false.	2007	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+ PDF Chat	Inverse conjecture for the gowers norm is false	2008	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+	Random low-degree polynomials are hard to approximate	2011	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+ PDF Chat	Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime	2014	Hamed Hatami Shachar Lovett
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2007	Ben Green Terence Tao
+	XOR Lemmas for Resilient Functions Against Polynomials.	2019	Eshan Chattopadhyay Pooya Hatami Kaave Hosseini Shachar Lovett David Zuckerman
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2009	Ben Joseph Green Terence Tao
+ PDF Chat	Estimating the Gowers Norm of Modulo Functions over Prime Fields	2012	Akinori Kawachi Hidetoki Tanaka Osamu Watanabe
+	Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime	2011	Hamed Hatami Shachar Lovett
+	Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime	2011	Hamed Hatami Shachar Lovett
+ PDF Chat	None	2011	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+	Pseudorandom Bits for Polynomials	2010	Andrej Bogdanov Emanuele Viola
+ PDF Chat	Local decoding and testing of polynomials over grids	2020	Mitali Bafna Srikanth Srinivasan Madhu Sudan
+	Low Degree Testing over the Reals	2022	Vipul Arora Arnab Bhattacharyya Noah Fleming Esty Kelman Yuichi Yoshida
+	On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity	2021	Subhamoy Maitra Chandra Sekhar Mukherjee Pantelimon Stănică Deng Tang
+	On the Weak mod m Representation of Boolean Functions	1995	Vince Grolmusz
+	Algorithmic regularity for polynomials and applications	2015	Arnab Bhattacharyya Pooya Hatami Madhur Tulsiani

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (12)

Action	Title	Year	Authors
+ PDF Chat	AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM	2008	Ben Green Terence Tao
+	None	2009	Charanjit S. Jutla Anindya C. Patthak Atri Rudra David Zuckerman
+ PDF Chat	Estimation of certain exponential sums arising in complexity theory	2005	Jean Bourgain
+	Theory and application of trapdoor functions	1982	Andrew Chi-Chih Yao
+ PDF Chat	Bounds on an exponential sum arising in Boolean circuit complexity	2005	Frederic Green Amitabha Roy Howard Straubing
+	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
+ PDF Chat	The inverse conjecture for the Gowers norm over finite fields via the correspondence principle	2010	Terence Tao Tamar Ziegler
+	Theory and application of trapdoor functions	1982	Andrew Chi-Chih Yao
+	An improved bound on correlation between polynomials over Z_m and MOD_q.	2006	Arkadev Chattopadhyay