The correct exponent for the Gotsman-Linial conjecture

DOI10.1007/S00037-014-0086-ZMaRDI QIDQ488047zbMATH OpenOpenAlexWikidataFDO

Authors Daniel M. Kane

Publication date 23 January 2015

Published in Computational Complexity (Search for Journal in Brave)

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

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)

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)$.

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

Cites work

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

Cited in

(11)

• 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
• Singularity of the \(k\)-core of a random graph
• Anticoncentration for subgraph statistics
• Low correlation noise stability of symmetric sets
• Multiplicative structures and random walks in o-minimal groups
• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• What circuit classes can be learned with non-trivial savings?
• Geometric and o-minimal Littlewood-Offord problems
• Anti-concentration Inequalities for Polynomials

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)