The correct exponent for the Gotsman-Linial conjecture

DOI10.1007/S00037-014-0086-ZzbMATH Open1314.68138arXiv1210.1283OpenAlexW2071833075WikidataQ123333173 ScholiaQ123333173MaRDI QIDQ488047FDOQ488047

Authors: Daniel M. Kane 

Publication date: 23 January 2015

Published in: Computational Complexity (Search for Journal in Brave)

Abstract: We prove a new bound on the average sensitivity of polynomial threshold functions. In particular we show that a polynomial threshold function of degree $d$ in at most $n$ variables has average sensitivity at most $sqrtn(log(n){)}^{O(dlog(d))}{2}^{O(d^{2}log(d)}$. For fixed $d$ the exponent in terms of $n$ in this bound is known to be optimal. This bound makes significant progress towards the Gotsman-Linial Conjecture which would put the correct bound at $Theta(dsqrtn)$.

Full work available at URL: https://arxiv.org/abs/1210.1283

Recommendations

• The Gotsman-Linial Conjecture is False
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Bounding the sensitivity of polynomial threshold functions
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions

zbMATH Keywords

noise sensitivitypolynomial threshold function

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
• The free Markoff field
• Gaussian Hilbert Spaces
• Spectral properties of threshold functions
• Gaussian bounds for noise correlation of functions
• Noise stability of functions with low influences: invariance and optimality
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Bounding the sensitivity of polynomial threshold functions
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
• A Small PRG for Polynomial Threshold Functions of Gaussians

Cited In (11)

• Singularity of the \(k\)-core of a random graph
• Geometric and o-minimal Littlewood-Offord problems
• Anti-concentration Inequalities for Polynomials
• Anticoncentration for subgraph statistics
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• What Circuit Classes Can Be Learned with Non-Trivial Savings?
• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• Multiplicative structures and random walks in o-minimal groups
• Bounding the sensitivity of polynomial threshold functions
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Low correlation noise stability of symmetric sets

This page was built for publication: The correct exponent for the Gotsman-Linial conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488047)