Fetching the paper…
Reading the bibliography…
Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n.
The identity of weak and strong extensions of differential operators
Kurt Otto Friedrichs · 1944
Earlier work this paper cites.
Bounds for the moments of linear and quadratic forms in independent variables
Peter Whittle · 1960
Earlier work this paper cites.
Étude des coefficients de Fourier des fonctions de L p ( G ) L^{p}(G)
Aline Bonami · 1970
Earlier work this paper cites.
Inequalities in Fourier analysis
William Beckner · 1975
Earlier work this paper cites.
The best constants in the Khintchine inequality
Uffe Haagerup · 1982
Earlier work this paper cites.
A fast and simple randomized parallel algorithm for the maximal independent set problem
Noga Alon, László Babai, and Alon Itai · 1986
Earlier work this paper cites.
Perceptrons
Marvin A. Minsky and Seymour L. Papert · 1988
Earlier work this paper cites.
On the power of two-point based sampling
Benny Chor and Oded Goldreich · 1989
Earlier work this paper cites.
Harmonic analysis of polynomial threshold functions
Jehoshua Bruck · 1990
Earlier work this paper cites.
Pseudorandom bits for constant depth circuits
Noam Nisan · 1991
Earlier work this paper cites.
Polynomial threshold functions, AC 0 functions and spectral norms
Jehoshua Bruck and Roman Smolensky · 1992
Earlier work this paper cites.
Majority gates vs. general weighted threshold gates
Mikael Goldmann, Johan Håstad, and Alexander A. Razborov · 1992
Earlier work this paper cites.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán · 1993
Earlier work this paper cites.
Slicing the hypercube
Michael E. Saks · 1993
Earlier work this paper cites.
The expressive power of voting polynomials
James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich · 1994
Cited alongside, same era.
Perceptrons, PP, and the Polynomial Hierarchy
Richard Beigel · 1994
Cited alongside, same era.
The communication complexity of threshold gates
Noam Nisan · 1994
Cited alongside, same era.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X. Goemans and David P. Williamson · 1995
Cited alongside, same era.
Derandomizing semidefinite programming based approximation algorithms
Sanjeev Mahajan and Ramesh Hariharan · 1995
Cited alongside, same era.
Computing boolean functions by polynomials and threshold circuits
Matthias Krause and Pavel Pudlák · 1998
Cited alongside, same era.
Extremal properties of polynomial threshold functions
Ryan O’Donnell and Rocco A. Servedio · 2008
Later among the works it cites.
The sign-rank of A C 0 AC^{0}
Alexander A. Razborov and Alexander A. Sherstov · 2008
Later among the works it cites.
Randomly supported independence and resistance
Per Austrin and Johan Håstad · 2009
Closest in time.
Poly-logarithmic independence fools AC 0 \mathrm{AC}^{0} circuits
Mark Braverman · 2009
Closest in time.
Bounded independence fools halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola · 2009
Closest in time.
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Distributional and L q L^{q} norm inequalities for polynomials over convex bodies in ℝ n \mathbb{R}^{n}
Anthony Carbery and James Wright · 2001
Cited alongside, same era.
How to integrate a polynomial over a sphere
Gerald B. Folland · 2001
Cited alongside, same era.
Algorithmic derandomization via complexity theory
D. Sivakumar · 2002
Cited alongside, same era.
Learning intersections and thresholds of halfspaces
Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio · 2004
Cited alongside, same era.
Learning DNF in time 2 O ~ ( n 1 / 3 ) {}^{\tilde{O}(n^{1/3})}
Adam R. Klivans and Rocco A. Servedio · 2004
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
Closest in time.
A simple proof of Bazzi’s theorem
Alexander A. Razborov · 2009
Closest in time.
The intersection of two halfspaces has high threshold degree
Alexander A. Sherstov · 2009
Closest in time.
Introduction to Linear Algebra
Gilbert Strang · 2009
Closest in time.
Fooling functions of halfspaces under product distributions
Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman · 2010
Closest in time.
An invariance principle for polytopes
Prahladh Harsha, Adam Klivans, and Raghu Meka · 2010
Closest in time.
On the exact space complexity of sketching and streaming small norms
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Closest in time.
Pseudorandom generators for polynomial threshold functions
Raghu Meka and David Zuckerman · 2010
Closest in time.
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz · 2010
Closest in time.