Hard Functions for Low-Degree Polynomials over Prime Fields

Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka

Type: Book-Chapter

Publication Date: 2011-01-01

Citations: 1

DOI: https://doi.org/10.1007/978-3-642-22993-0_14

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Hard Functions for Low-Degree Polynomials over Prime Fields	2013	Andrej Bogdanov Akinori Kawachi Hidetoki Tanaka
+	Inverse Conjecture for the Gowers norm is false	2007	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+	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
+ PDF Chat	Inverse conjecture for the gowers norm is false	2008	Shachar Lovett Roy Meshulam Alex Samorodnitsky
+ PDF Chat	Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime	2014	Hamed Hatami Shachar Lovett
+	Random low-degree polynomials are hard to approximate	2011	Ido Ben‐Eliezer Rani Hod 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
+ 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
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2009	Ben Joseph Green Terence Tao
+ 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
+	On the Weak mod m Representation of Boolean Functions	1995	Vince Grolmusz
+	Low Degree Testing over the Reals	2022	Vipul Arora Arnab Bhattacharyya Noah Fleming Esty Kelman Yuichi Yoshida
+ PDF Chat	Quadratic Goldreich--Levin Theorems	2014	Madhur Tulsiani Julia Wolf
+	Every locally characterized affine-invariant property is testable	2012	Arnab Bhattacharyya Eldar Fischer Hamed Hatami Pooya Hatami Shachar Lovett

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Estimating the Gowers Norm of Modulo Functions over Prime Fields	2012	Akinori Kawachi Hidetoki Tanaka Osamu Watanabe

Works Cited by This (11)

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
+	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
+ PDF Chat	Low-degree tests at large distances	2007	Alex Samorodnitsky