Fooling Polytopes
From MaRDI portal
Recommendations
Cites work
- A polynomial bound in Freiman's theorem.
- A random-sampling-based algorithm for learning intersections of halfspaces
- A simple proof of Bazzi's theorem
- A Small PRG for Polynomial Threshold Functions of Gaussians
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Almost Optimal Pseudorandom Generators for Spherical Caps
- An entropic proof of Chang's inequality
- An invariance principle for polytopes
- Analysis of Boolean Functions
- Bounded Independence Fools Halfspaces
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Concentration of Measure for the Analysis of Randomized Algorithms
- Cryptographic hardness for learning intersections of halfspaces
- DNF sparsification and a faster deterministic counting algorithm
- Estimates of the Moments of Sums of Independent Random Variables
- Every linear threshold function has a low-weight approximator
- Explicit dimension reduction and its applications
- Fooling polytopes
- Hardness vs randomness
- How much are increasing sets positively correlated?
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 46318 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 1975229 (Why is no real title available?)
- scientific article; zbMATH DE number 7250142 (Why is no real title available?)
- scientific article; zbMATH DE number 3099315 (Why is no real title available?)
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- Learning intersections and thresholds of halfspaces
- New degree bounds for polynomial threshold functions
- On a lemma of Littlewood and Offord
- On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
- On Littlewood's estimate for the binomial distribution
- On the hardness of learning intersections of two halfspaces
- On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
- Polylogarithmic independence can fool DNF formulas
- PP is closed under intersection
- Pseudorandom bits for constant depth circuits
- Pseudorandom generators for space-bounded computation
- Pseudorandomness for network algorithms
- Pseudorandomness via the discrete Fourier transform
- Randomness is linear in space
- Simple and efficient pseudorandom generators from gaussian processes
- Smooth approximations of the norm and differentiable functions with bounded support in Banach space \(\ell ^ k_{\infty}\)
- Solution of the Littlewood-Offord problem in high dimensions
- The average sensitivity of an intersection of half spaces
- The Chow parameters problem
- The intersection of two halfspaces has high threshold degree
- The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
- What circuit classes can be learned with non-trivial savings?
Cited in
(3)
This page was built for publication: Fooling Polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066946)
