Average sensitivity and noise sensitivity of polynomial threshold functions

Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan

Type: Preprint

Publication Date: 2009-01-01

Citations: 11

DOI: https://doi.org/10.48550/arxiv.0909.5011

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Bounding the Sensitivity of Polynomial Threshold Functions	2014	Prahladh Harsha Adam R. Klivans Raghu Meka
+ PDF Chat	The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions	2010	Daniel M. Kane
+	Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise	2023	Shiwei Zeng Jie Shen
+	Efficient deterministic approximate counting for low-degree polynomial threshold functions	2013	Anindya De Rocco A. Servedio
+	Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)	2018	Ilias Diakonikolas Daniel M. Kane
+	Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)	2018	Ilias Diakonikolas Daniel M. Kane
+ PDF Chat	Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)	2019	Ilias Diakonikolas Daniel M. Kane
+ PDF Chat	The Correct Exponent for the Gotsman-Linial Conjecture	2013	Daniel M. Kane
+	Detecting Low-Degree Truncation	2024	Anindya De Huan Li Shivam Nadimpalli Rocco A. Servedio
+ PDF Chat	Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs	2024	Ilias Diakonikolas Daniel M. Kane Vasilis Kontonis Sihan Liu Nikos Zarifis
+ PDF Chat	Detecting Low-Degree Truncation	2024	Anindya De Huan Li Shivam Nadimpalli Rocco A. Servedio
+	Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs	2024	Ilias Diakonikolas D. Kane Vasilis Kontonis Sihan Liu Nikos Zarifis
+ PDF Chat	The Robust Sensitivity of Boolean Functions	2018	Shachar Lovett Avishay Tal Jiapeng Zhang
+	The Correct Exponent for the Gotsman-Linial Conjecture	2012	Daniel M. Kane
+ PDF Chat	The correct exponent for the Gotsman–Linial Conjecture	2014	Daniel M. Kane
+ PDF Chat	None	2014	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+	Efficient deterministic approximate counting for low degree polynomial threshold functions.	2013	Anindya De Rocco A. Servedio
+	A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions	2009	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+	Degree and Sensitivity: tails of two distributions	2016	Parikshit Gopalan Rocco A. Servedio Avishay Tal Avi Wigderson
+	Degree and Sensitivity: tails of two distributions.	2016	Parikshit Gopalan Rocco A. Servedio Avishay Tal Avi Wigderson

Works That Cite This (10)

Action	Title	Year	Authors
+	A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions	2009	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+ PDF Chat	The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions	2010	Daniel M. Kane
+	Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.	2013	Anindya De Ilias Diakonikolas Rocco A. Servedio
+ PDF Chat	A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions	2010	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+	Concentration and Moment Inequalities for Polynomials of Independent Random Variables	2012	Warren Schudy Maxim Sviridenko
+ PDF Chat	None	2014	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+ PDF Chat	Bounding the Sensitivity of Polynomial Threshold Functions	2014	Prahladh Harsha Adam R. Klivans Raghu Meka
+	An elementary proof of anti-concentration of polynomials in Gaussian variables.	2010	Shachar Lovett
+	Concentration and moment inequalities for polynomials of independent random variables	2012	Warren Schudy Maxim Sviridenko
+	Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions	2013	Anindya De Ilias Diakonikolas Rocco A. Servedio

Works Cited by This (8)

Action	Title	Year	Authors
+ PDF Chat	Noise Stability of Weighted Majority	2020	Yuval Peres
+ PDF Chat	Spectral properties of threshold functions	1994	Craig Gotsman Nathan Linial
+ PDF Chat	Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in ${\Bbb R}^n$	2001	Anthony Carbery James Wright
+ PDF Chat	Quantitative noise sensitivity and exceptional times for percolation	2010	Oded Schramm Jeffrey E. Steif
+ PDF Chat	On the noise sensitivity of monotone functions	2003	Elchanan Mossel Ryan O’Donnell
+	Noise Sensitivity of Boolean Functions and Applications to Percolation	2011	Itaı Benjamini Gn. Kalai Oded Schramm
+	On the fourier tails of bounded functions over the discrete cube	2006	Irit Dinur Ehud Friedgut Guy Kindler Ryan O’Donnell
+	Improved Approximation of Linear Threshold Functions	2009	Ilias Diakonikolas Rocco A. Servedio