Half-Spaces with Influential Variable

DOI10.1137/S0040585X97T989866zbMath1434.68196OpenAlexW3002187646MaRDI QIDQ5107661

Friedrich Götze, Dainius Dzindzalieta

Publication date: 28 April 2020

Published in: Theory of Probability & Its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0040585x97t989866

zbMATH Keywords

Boolean functionsinfluencelinear threshold functionsBoolean cubesmall ball inequalities

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Randomized algorithms (68W20)

Related Items (2)

Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Proof of Tomaszewski's conjecture on randomly signed sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random embedding of \({\ell_p^n}\) into \({\ell_r^N}\)
• On the product of sign vectors and unit vectors
• A note on random signs
• A tight Gaussian bound for weighted sums of Rademacher random variables
• Threshold circuits of bounded depth
• Smallest singular value of random matrices and geometry of random polytopes
• Testing Halfspaces
• Property testing and its connection to learning and approximation
• The Perceptron: A Model for Brain Functioning. I
• A new series of conjectures and open questions in optimization and matrix analysis
• Smallest singular value of a random rectangular matrix
• Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Refinement of the Remainder in the Lyapunov Theorem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Algorithmic Learning Theory

This page was built for publication: Half-Spaces with Influential Variable