Bounded Independence Fools Halfspaces

DOI10.1137/100783030zbMath1221.68169OpenAlexW2148858749MaRDI QIDQ5390601

Ilias Diakonikolas, Ragesh Jaiswal, Parikshit Gopalan, Emanuele Viola, Rocco A. Servedio

Publication date: 4 April 2011

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

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

zbMATH Keywords

pseudorandom generatorhalfspacelinear threshold function\(k\)-wise independent distributionreal approximation theory

Mathematics Subject Classification ID

Related Items (26)

On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace ⋮ Making the Long Code Shorter ⋮ A dichotomy for local small-bias generators ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Cryptographic hardness of random local functions. Survey ⋮ Fooling Polytopes ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Improved approximation of linear threshold functions ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Approximation of \(\operatorname{sgn} (x)\) on two symmetric intervals by rational functions with fixed poles ⋮ Polynomial approximation on disjoint segments and amplification of approximation ⋮ On the Power of Statistical Zero Knowledge ⋮ Bounded Independence Plus Noise Fools Products ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Unnamed Item ⋮ Simple and efficient pseudorandom generators from gaussian processes ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ 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: Bounded Independence Fools Halfspaces