Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

DOI10.1137/110855223zbMath1311.68081OpenAlexW1486564402MaRDI QIDQ5419037

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

Publication date: 4 June 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/19352444/Diakonikolas_Raghavendra_ET_AL_2014_Average_Sensitivity_and_noise_sensitivity_of_polynomial_threshold_functions.pdf

zbMATH Keywords

Fourier analysisnoise sensitivityBoolean functionaverage sensitivitypolynomial threshold function

Mathematics Subject Classification ID

Related Items (9)

Separation results for Boolean function classes ⋮ Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Upper bounds on Fourier entropy ⋮ Upper Bounds on Fourier Entropy ⋮ The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ The correct exponent for the Gotsman-Linial conjecture ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Concentration and Moment Inequalities for Polynomials of Independent Random Variables

This page was built for publication: Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions