Fooling Polytopes
From MaRDI portal
Publication:5066946
DOI10.1145/3460532OpenAlexW4210243870MaRDI QIDQ5066946
Ryan O'Donnell, Li-Yang Tan, Rocco A. Servedio
Publication date: 31 March 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3460532
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Learning intersections and thresholds of halfspaces
- On the hardness of learning intersections of two halfspaces
- Pseudorandom bits for constant depth circuits
- Solution of the Littlewood-Offord problem in high dimensions
- Pseudorandom generators for space-bounded computation
- Hardness vs randomness
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- A polynomial bound in Freiman's theorem.
- PP is closed under intersection
- Randomness is linear in space
- How much are increasing sets positively correlated?
- Smooth approximations of the norm and differentiable functions with bounded support in Banach space \(\ell ^ k_{\infty}\)
- The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
- Every linear threshold function has a low-weight approximator
- Cryptographic hardness for learning intersections of halfspaces
- On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
- On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
- Pseudorandomness for network algorithms
- Pseudorandom Generators for Polynomial Threshold Functions
- Explicit Dimension Reduction and Its Applications
- Almost Optimal Pseudorandom Generators for Spherical Caps
- A Simple Proof of Bazzi’s Theorem
- A random-sampling-based algorithm for learning intersections of halfspaces
- The Chow Parameters Problem
- Polylogarithmic Independence Can Fool DNF Formulas
- Estimates of the Moments of Sums of Independent Random Variables
- On Littlewood's estimate for the binomial distribution
- Pseudorandomness via the Discrete Fourier Transform
- What Circuit Classes Can Be Learned with Non-Trivial Savings?
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- An Entropic Proof of Chang's Inequality
- Simple and efficient pseudorandom generators from gaussian processes
- Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
- Analysis of Boolean Functions
- Fooling polytopes
- The average sensitivity of an intersection of half spaces
- Bounded Independence Fools Halfspaces
- An invariance principle for polytopes
- The Intersection of Two Halfspaces Has High Threshold Degree
- A Small PRG for Polynomial Threshold Functions of Gaussians
- On a lemma of Littlewood and Offord
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- New degree bounds for polynomial threshold functions
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Fooling Polytopes
