NDLI: Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Raghavendra, Prasad Diakonikolas, Ilias Servedio, Rocco A. Tan, Li-Yang
Copyright Year	2014
Abstract	We give the first nontrivial upper bounds on the Boolean average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). Our bound on the Boolean average sensitivity of PTFs represents the first progress toward the resolution of a conjecture of Gotsman and Linial [Combinatorica, 14 (1994), pp. 35--50], which states that the symmetric function slicing the middle $d$ layers of the Boolean hypercube has the highest average sensitivity of all degree-$d$ PTFs. Via the $L_1$ polynomial regression algorithm of Kalai et al. [SIAM J. Comput., 37 (2008), pp. 1777--1805], our bound on Boolean noise sensitivity yields the first polynomial-time agnostic learning algorithm for the broad class of constant-degree PTFs under the uniform distribution. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the critical-index machinery of [R. Servedio, Comput. Complexity, 16 (2007), pp. 180--209] (which in that work applies to halfspaces, i.e., degree-1 PTFs) to general PTFs. Together with the invariance principle of [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Ann. of Math. (2), 171 (2010), pp. 295--341], this allows us to essentially reduce the Boolean setting to the Gaussian setting. The main ingredients used to obtain our bound in the Gaussian setting are tail bounds and anticoncentration bounds on low-degree polynomials in Gaussian random variables [S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997; A. Carbery and J. Wright, Math. Res. Lett., 8 (2001), pp. 233--248]. Our bound on Boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of Boolean PTFs to corresponding bounds on noise sensitivity.
Starting Page	231
Ending Page	253
Page Count	23
File Format	PDF
ISSN	00975397
DOI	10.1137/110855223
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010))
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-02-12
Access Restriction	Subscribed
Subject Keyword	Nonnumerical algorithms polynomial threshold function Boolean function Fourier analysis Complexity of computation Computational learning theory average sensitivity noise sensitivity
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

Average sensitivity and noise sensitivity of polynomial threshold functions

Social choice, computational complexity, Gaussian geometry, and Boolean functions

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions

The Power of Asymmetry in Constant-Depth Circuits

Projective cofactor decompositions of Boolean functions and the satisfiability problem

Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $

Extremal properties of polynomial threshold functions

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

Similar Documents

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

Average sensitivity and noise sensitivity of polynomial threshold functions

Social choice, computational complexity, Gaussian geometry, and Boolean functions

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions

The Power of Asymmetry in Constant-Depth Circuits

Projective cofactor decompositions of Boolean functions and the satisfiability problem

Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $

Extremal properties of polynomial threshold functions

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions