Fetching the paper…
Reading the bibliography…
The subject of this textbook is the analysis of Boolean functions.
Linear groups with an exposition of Galois field theory
Leonard Dickson · 1901
Earlier work this paper cites.
Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen
Albert Einstein · 1905
Earlier work this paper cites.
Zur Theorie der orthogonalen Funktionensysteme
Alfréd Haar · 1910
Earlier work this paper cites.
Leçons d’Analyse Fonctionnelle
Paul Lévy · 1922
Earlier work this paper cites.
Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung
Jarl Lindeberg · 1922
Earlier work this paper cites.
A closed set of normal orthogonal functions
Joseph Walsh · 1923
Earlier work this paper cites.
On a technique of calculating propositions in symbolic logic
Ivan Zhegalkin · 1927
Earlier work this paper cites.
Sur une généralisation des polynomes d’Hermite
Mikahil (Krawtchouk) Kravchuk · 1929
Earlier work this paper cites.
On the theory of the Brownian motion
George Uhlenbeck and Leonard Ornstein · 1930
Earlier work this paper cites.
A remarkable series of orthogonal functions (I)
Raymond Paley · 1932
Earlier work this paper cites.
The theory of relay circuit composition
Akira Nakashima · 1935
Earlier work this paper cites.
A symbolic analysis of relay and switching circuits
Claude Shannon · 1937
Earlier work this paper cites.
Some Mathematical Methods for the Construction and Simplification of Two-Terminal Electrical Networks of Class A
Victor Shestakov · 1938
Earlier work this paper cites.
The accuracy of the Gaussian approximation to the sum of independent variates
Andrew Berry · 1941
Earlier work this paper cites.
On the Liapounoff limit of error in the theory of probability
Carl-Gustav Esseen · 1942
Earlier work this paper cites.
The elementary statistics of majority voting
Lionel Penrose · 1946
Earlier work this paper cites.
Factorial experiments derivable from combinatorial arrangements of arrays
Calyampudi Rao · 1947
Earlier work this paper cites.
On a class of complete orthonormal systems
Naum Vilenkin · 1947
Earlier work this paper cites.
On the asymptotic distribution of differentiable statistical functions
Richard von Mises · 1947
Earlier work this paper cites.
A class of statistics with asymptotically normal distribution
Wassily Hoeffding · 1948
Earlier work this paper cites.
Die Brunn-Minkowskische Ungleichung und ihr Spiegelbild sowie die isoperimetrische Eigenschaft der Kugel in der euklidischen und nichteuklidischen Geometrie. I
Erhard Schmidt · 1948
Earlier work this paper cites.
On the Walsh functions
Nathan Fine · 1949
Earlier work this paper cites.
A difficulty in the concept of social welfare
Kenneth Arrow · 1950
Earlier work this paper cites.
Les théories de l’intérêt général et le problème logique de l’agrégation
George-Théodule Guilbaud · 1952
Earlier work this paper cites.
A set of independent necessary and sufficient conditions for simple majority decisions
Kenneth May · 1952
Earlier work this paper cites.
On certain sets of integers
Klaus Roth · 1953
Earlier work this paper cites.
A value for n n -person games
Lloyd Shapley · 1953
Earlier work this paper cites.
Application of Boolean algebra to switching circuit design and to error detection
David Muller · 1954
Earlier work this paper cites.
Boolean algebras in electric circuit design
David Muller · 1954
Earlier work this paper cites.
Percolation processes I. Crystals and mazes
Simon Broadbent and John Hammersley · 1957
Earlier work this paper cites.
The existence of social welfare functions
Julian Blau · 1957
Earlier work this paper cites.
A theory of the coordinate representations of switching functions
Ichizo Ninomiya · 1958
Earlier work this paper cites.
Approximation of semi-groups of operators
Hale Trotter · 1958
Earlier work this paper cites.
On random graphs I
Paul Erdős and Alfréd Rényi · 1959
Earlier work this paper cites.
On the classification of Boolean functions
Solomon Golomb · 1959
Earlier work this paper cites.
On the characterization of threshold functions
Chao-Kong Chow · 1961
Earlier work this paper cites.
Truth functions realizable by single threshold organs
Calvin Elgot · 1961
Earlier work this paper cites.
Voting and the summation of preferences: An interpretive bibliographic review of selected developments during the last decade
William Riker · 1961
Earlier work this paper cites.
Realizations of linear functions by formulas using ∨ \vee , &, ¯ \overline{\ }
Bella Subbotovskaya · 1961
Earlier work this paper cites.
The establishment of a unique representation for a linearly separable function
Meyer Tannenbaum · 1961
Earlier work this paper cites.
Fourier analysis on groups
Walter Rudin · 1962
Earlier work this paper cites.
Correlation properties of cyclic sequences
Robert Titsworth · 1962
Earlier work this paper cites.
Social choice and individual values
Kenneth Arrow · 1963
Earlier work this paper cites.
Affine equivalence of switching functions
Robert Lechner · 1963
Earlier work this paper cites.
Optimal ranging codes
Robert Titsworth · 1963
Earlier work this paper cites.
Optimal assignments of numbers to vertices
Lawrence Harper · 1964
Earlier work this paper cites.
Multipliers for Walsh–Fourier series
Chinami Watari · 1964
Earlier work this paper cites.
Weighted voting doesn’t work: A mathematical analysis
John Banzhaf · 1965
Earlier work this paper cites.
Estimates of the remainder in a combinatorial central limit theorem
Algimantas Bikelis · 1966
Earlier work this paper cites.
Families of non-disjoint subsets
Daniel Kleitman · 1966
Earlier work this paper cites.
A quartic interaction in two dimensions
Edward Nelson · 1966
Earlier work this paper cites.
Fermeture en probabilité des chaos de Wiener
Michel Schreiber · 1967
Earlier work this paper cites.
Ensembles Λ ( p ) {\Lambda}(p) dans le dual de D ∞ {D}^{\infty}
Aline Bonami · 1968
Earlier work this paper cites.
The paradox of voting: probability calculations
Mark Garman and Morton Kamien · 1968
Earlier work this paper cites.
Boson fields with nonlinear selfinteraction in two dimensions
James Glimm · 1968
Earlier work this paper cites.
Asymptotic normality of simple linear rank statistics under alternatives
Jaroslav Hájek · 1968
Earlier work this paper cites.
Some random series of functions
Jean-Pierre Kahane · 1968
Earlier work this paper cites.
On norms of idempotent measures
Sadahiro Saeki · 1968
Earlier work this paper cites.
Partially alternate derivation of a result of Nelson
Paul Federbush · 1969
Earlier work this paper cites.
Über Produkte von quadratisch integrierbaren Funktionen endlicher Vielfalt
Konrad Kiener · 1969
Earlier work this paper cites.
Fermeture en probabilité de certains sous-espaces d’un espace L 2 L^{2} . Application aux chaos de Wiener
Michel Schreiber · 1969
Earlier work this paper cites.
Étude des coefficients Fourier des fonctions de L p ( G ) L^{p}(G)
Aline Bonami · 1970
Earlier work this paper cites.
On the nonexistence of uniform homeomorphisms between l p l_{p} -spaces
Per Enflo · 1970
Earlier work this paper cites.
Construction of non-linear local quantum processes: I
Irving Segal · 1970
Earlier work this paper cites.
Control of collectivities and the power of a collectivity to act
John Coleman · 1971
Earlier work this paper cites.
Harmonic analysis of switching functions
Robert Lechner · 1971
Earlier work this paper cites.
A survey of bent functions
John Dillon · 1972
Earlier work this paper cites.
Existence and uniqueness of physical ground states
Leonard Gross · 1972
Earlier work this paper cites.
Special functions & their applications
Nikolaĭ Lebedev · 1972
Earlier work this paper cites.
Hypercontractive semigroups and two dimensional self-coupled Bose fields
Barry Simon and Raphael Høegh-Krohn · 1972
Earlier work this paper cites.
A bound for the error in the normal approximation to the distribution of a sum of dependent random variables
Charles Stein · 1972
Earlier work this paper cites.
Series with respect to the Walsh system and their generalizations
Leonid Balashov and Aleksandr Rubinshtein · 1973
Earlier work this paper cites.
Limit theorems for random quadratic forms
Vyacheslav Girko · 1973
Earlier work this paper cites.
Geometry of differential space
Henry McKean · 1973
Earlier work this paper cites.
Intersection des mesures spectrales conjuguées
Tamás Matolcsi and József Szücs · 1973
Earlier work this paper cites.
The free Markoff field
Edward Nelson · 1973
Earlier work this paper cites.
Some limit theorems for polynomials of second order
Vladimir Rotar’ · 1973
Earlier work this paper cites.
Approximation algorithms for combinatorial problems
David Johnson · 1974
Earlier work this paper cites.
Probabilistic characteristics of graphs with large connectivity
Grigory Margulis · 1974
Earlier work this paper cites.
Some limit theorems for polynomials of second degree
Vladimir Rotar’ · 1974
Earlier work this paper cites.
Extremal properties of half-spaces for spherically invariant measures
Vladimir Sudakov and Boris Tsirel’son · 1974
Earlier work this paper cites.
Inequalities in Fourier analysis
William Beckner · 1975
Earlier work this paper cites.
The Brunn–Minkowski inequality in Gauss space
Christer Borell · 1975
Earlier work this paper cites.
Logarithmic Sobolev inequalities
Leonard Gross · 1975
Earlier work this paper cites.
Limit theorems for multilinear forms and quasipolynomial functions
Vladimir Rotar’ · 1975
Earlier work this paper cites.
On sequences of pairs of dependent random variables
Hans Witsenhausen · 1975
Earlier work this paper cites.
Spreading of sets in product spaces and hypercontraction of the Markov operator
Rudolf Ahlswede and Péter Gács · 1976
Earlier work this paper cites.
Best constants in Young’s inequality, its converse, and its generalization to more than three functions
Herm Brascamp and Elliott Lieb · 1976
Earlier work this paper cites.
Spherical rearrangements, subharmonic functions, and ∗ * -functions in n n -space
Albert Baernstein and Bert Taylor · 1976
Earlier work this paper cites.
Finite orthogonal series in the design of digital devices: analysis, synthesis, and optimization
Mark Karpovsky · 1976
Earlier work this paper cites.
Sur l’espérance conditionnelle par rapport à un mouvement brownien
Jacques Neveu · 1976
Earlier work this paper cites.
Convolution by a biased coin
Haskell Rosenthal · 1976
Earlier work this paper cites.
On “bent” functions
Oscar Rothaus · 1976
Earlier work this paper cites.
The dimension of almost spherical sections of convex bodies
Tadeusz Figiel, Joram Lindenstrauss, and Vitali Milman · 1977
Earlier work this paper cites.
New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities
Robert McEliece, Eugene Rodemich, Howard Rumsey, and Lloyd Welch · 1977
Earlier work this paper cites.
The theory of error-correcting codes
F. Jessie MacWilliams and Neil Sloane · 1977
Earlier work this paper cites.
Probabilistic computations: Towards a unified measure of complexity
Andrew Yao · 1977
Earlier work this paper cites.
On the limit theorems for random variables with values in the spaces l p l_{p} ( 2 ≤ p < ∞ ) (2\leq p<\infty)
Gilles Pisier and Joel Zinn · 1978
Earlier work this paper cites.
Gross’s logarithmic Sobolev inequality: a simple proof
Robert Adams and Frank Clarke · 1979
Earlier work this paper cites.
On the integrability of Banach space valued Walsh polynomials
Christer Borell · 1979
Earlier work this paper cites.
Walsh subspaces of l p l^{p} product spaces
Jean Bourgain · 1979
Earlier work this paper cites.
Fast probabilistic algorithms
Rūsi n · 1979
Earlier work this paper cites.
Limit theorems for polylinear forms
Vladimir Rotar’ · 1979
Earlier work this paper cites.
Two-point inequalities, the Hermite semigroup, and the Gauss–Weierstrass semigroup
Fred Weissler · 1979
Earlier work this paper cites.
Asymptotic distribution of symmetric statistics
Herman Rubin and Richard Vitale · 1980
Earlier work this paper cites.
Logarithmic Sobolev inequalities and hypercontractive estimates on the circle
Fred Weissler · 1980
Earlier work this paper cites.
The jackknife estimate of variance
Bradley Efron and Charles Stein · 1981
Earlier work this paper cites.
On the critical percolation probabilities
Lucio Russo · 1981
Earlier work this paper cites.
Positivity improving operators and hypercontractivity
Christer Borell · 1982
Earlier work this paper cites.
The best constants in the Khinchine inequality
Uffe Haagerup · 1982
Earlier work this paper cites.
Spectral method of Boolean function complexity
Stanley Hurst, D. Michael Miller, and Jon Muzio · 1982
Earlier work this paper cites.
Applications of ANOVA type decompositions for comparisons of conditional variance statistics including jackknife estimates
Samuel Karlin and Yosef Rinott · 1982
Earlier work this paper cites.
The Byzantine generals problem
Leslie Lamport, Robert Shostak, and Marshall Pease · 1982
Earlier work this paper cites.
An approximate zero-one law
Lucio Russo · 1982
Earlier work this paper cites.
Σ 1 1 \Sigma^{1}_{1} -formulae on finite structures
Miklós Ajtai · 1983
Earlier work this paper cites.
Symétrisation dans l’espace de gauss
Antoine Ehrhard · 1983
Earlier work this paper cites.
Tensor analysis of ANOVA decomposition
Akimichi Takemura · 1983
Earlier work this paper cites.
Two-point symmetrization, the isoperimetric inequality on the sphere and some applications
Yoav Benyamini · 1984
Earlier work this paper cites.
Stein’s method and the Berry–Esseen theorem
Andrew Barbour and Peter Hall · 1984
Earlier work this paper cites.
An estimate of the remainder in a combinatorial central limit theorem
Erwin Bolthausen · 1984
Earlier work this paper cites.
On polynomial chaos and integrability
Christer Borell · 1984
Earlier work this paper cites.
Inégalités isopérimétriques et intégrales de Dirichlet gaussiennes
Antoine Ehrhard · 1984
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick Furst, James Saxe, and Michael Sipser · 1984
Earlier work this paper cites.
Correlation-immunity of nonlinear combining functions for cryptographic applications
Thomas Siegenthaler · 1984
Earlier work this paper cites.
A theory of the learnable
Leslie Valiant · 1984
Earlier work this paper cites.
An expansion for symmetric statistics and the Efron–Stein inequality
Richard Vitale · 1984
Earlier work this paper cites.
A fast and simple randomized algorithm for the maximal independent set problem
Noga Alon, László Babai, and Alon Itai · 1985
Earlier work this paper cites.
Diffusions hypercontractives
Dominiques Bakry and Michel Émery · 1985
Earlier work this paper cites.
Collective coin flipping, robust voting schemes and minima of Banzhaf values
Michael Ben-Or and Nathan Linial · 1985
Earlier work this paper cites.
Geometric bounds on the Ornstein–Uhlenbeck velocity process
Christer Borell · 1985
Cited alongside, same era.
The bit extraction problem or t t -resilient functions
Benny Chor, Joel Friedman, Oded Goldreich, Johan Håstad, Steven Rudich, and Roman Smolensky · 1985
Cited alongside, same era.
Separating the polynomial time hierarchy by oracles
Andrew Yao · 1985
Cited alongside, same era.
Probabilistic methods in the geometry of Banach spaces
Gilles Pisier · 1986
Cited alongside, same era.
An Efron–Stein inequality for nonsymmetric statistics
J. Michael Steele · 1986
Cited alongside, same era.
Approximate computation of expectations
Charles Stein · 1986
Cited alongside, same era.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Later among the works it cites.
Property Testing, PCP, and juntas
Guy Kindler · 2002
Later among the works it cites.
Noise-resistant Boolean functions are juntas
Guy Kindler and Shmuel Safra · 2002
Later among the works it cites.
The geometric Kannan–Lovász–Simonovits lemma, dimension-free estimates for volumes of sublevel sets of polynomials, and distribution of zeros of random analytic functions
Fedor Nazarov, Mikhail Sodin, and Alexander Vol’berg · 2002
Later among the works it cites.
Testing basic Boolean formulae
Michal Parnas, Dana Ron, and Alex Samorodnitsky · 2002
Later among the works it cites.
Computer assisted proof of optimal approximability results
Uri Zwick · 2002
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Probabilistic Boolean decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson · 1986
Cited alongside, same era.
Occam’s razor
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth · 1987
Cited alongside, same era.
Generic oracles and oracle classes
Manuel Blum and Russell Impagliazzo · 1987
Cited alongside, same era.
Spectral lower-bound techniques for logic circuits
Yigal Brandman · 1987
Cited alongside, same era.
Threshold functions
Béla Bollobás and Andrew Thomason · 1987
Cited alongside, same era.
On the influence of single participant in coin flipping schemes
Benny Chor and Mihály Geréb-Graus · 1987
Cited alongside, same era.
Later among the works it cites.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2003
Later among the works it cites.
Learning a function of r r relevant variables
Avrim Blum · 2003
Later among the works it cites.
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson · 2003
Later among the works it cites.
Two applications of information complexity
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2003
Later among the works it cites.
On the maximal perimeter of a convex set in ℝ n \mathbb{R}^{n} with respect to a Gaussian measure
Fedor Nazarov · 2003
Later among the works it cites.
Computational applications of noise sensitivity
Ryan O’Donnell · 2003
Later among the works it cites.
On a nonsymmetric version of the Khinchine–Kahane inequality
Krzysztof Oleszkiewicz · 2003
Later among the works it cites.
A Lyapunov type bound in 𝐑 d \mathbf{R}^{d}
Vidmantas Bentkus · 2004
Later among the works it cites.
Robust PCPs of proximity, shorter PCPs and applications to coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan · 2004
Later among the works it cites.
Maximizing quadratic programs: extending Grothendieck’s Inequality
Moses Charikar and Anthony Wirth · 2004
Later among the works it cites.
On approximate graph colouring and MAX- k k -CUT algorithms based on the ϑ \vartheta -function
Etienne de Klerk, Dmitrii Pasechnik, and Johannes Warners · 2004
Later among the works it cites.
Assignment testers: Towards a combinatorial proof of the PCP Theorem
Irit Dinur and Omer Reingold · 2004
Later among the works it cites.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2004
Later among the works it cites.
Learning intersections and thresholds of halfspaces
Adam Klivans, Ryan O’Donnell, and Rocco Servedio · 2004
Later among the works it cites.
Exact quantum query complexity for total Boolean functions
Gatis Midrijānis · 2004
Later among the works it cites.
Learning functions of k k relevant variables
Elchanan Mossel, Ryan O’Donnell, and Rocco Servedio · 2004
Later among the works it cites.
Hardness amplification within NP
Ryan O’Donnell · 2004
Later among the works it cites.
Noise stability of weighted majority
Yuval Peres · 2004
Later among the works it cites.
On the (im)possibility of non-interactive correlation distillation
Ke Yang · 2004
Later among the works it cites.
On non-approximability for quadratic programs
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra · 2005
Later among the works it cites.
The two possible values of the chromatic number of a random graph
Dimitris Achlioptas and Assaf Naor · 2005
Later among the works it cites.
Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read
Itai Benjamini, Oded Schramm, and David Wilson · 2005
Later among the works it cites.
Hunting for sharp thresholds
Ehud Friedgut · 2005
Later among the works it cites.
Inapproximability results via Long Code based PCPs
Subhash Khot · 2005
Later among the works it cites.
The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ 1 \ell_{1}
Subhash Khot and Nisheeth Vishnoi · 2005
Later among the works it cites.
Coin flipping from a cosmic source: On error correction of truly random bits
Elchanan Mossel and Ryan O’Donnell · 2005
Later among the works it cites.
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz · 2005
Later among the works it cites.
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz · 2005
Later among the works it cites.
Isomorphisms between H 1 H^{1} spaces
Paul Müller · 2005
Later among the works it cites.
Every decision tree has an influential variable
Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco Servedio · 2005
Later among the works it cites.
The RPR 2 rounding technique for semidefinite programs
Uriel Feige and Michael Langberg · 2006
Later among the works it cites.
SDP gaps and UGC-hardness for Max-Cut-Gain
Subhash Khot and Ryan O’Donnell · 2006
Later among the works it cites.
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, and Mario Szegedy · 2006
Later among the works it cites.
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami–Beckner inequality
Elchanan Mossel, Ryan O’Donnell, Oded Regev, Jeffrey Steif, and Benjamin Sudakov · 2006
Later among the works it cites.
Learning monotone decision trees in polynomial time
Ryan O’Donnell and Rocco Servedio · 2006
Later among the works it cites.
Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
Raphaël Rossignol · 2006
Later among the works it cites.
Regularization from l 1 l^{1} by convolution
Michel Talagrand · 2006
Later among the works it cites.
Balanced Max- 2 2 Sat might not be hardest
Per Austrin · 2007
Later among the works it cites.
Pseudorandom bits for polynomials
Andrej Bogdanov and Emanuele Viola · 2007
Later among the works it cites.
On the Fourier tails of bounded functions over the discrete cube
Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell · 2007
Later among the works it cites.
The PCP Theorem by gap amplification
Irit Dinur · 2007
Later among the works it cites.
Edge-isoperimetric inequalities and influences
Dvir Falik and Alex Samorodnitsky · 2007
Later among the works it cites.
Thresholds and expectation thresholds
Jeff Kahn and Gil Kalai · 2007
Later among the works it cites.
Optimal inapproximability results for Max-Cut and other 2 2 -variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Later among the works it cites.
Short-time heat flow and functions of bounded variation in ℝ N \mathbb{R}^{N}
Michele Miranda Jr., Diego Pallara, Fabio Paronetto, and Marc Preunkert · 2007
Later among the works it cites.
Learning monotone decision trees in polynomial time
Ryan O’Donnell and Rocco Servedio · 2007
Later among the works it cites.
Hypercontractivity of simple random variables
Paweł Wolff · 2007
Later among the works it cites.
How to solve longstanding open problems in quantum computing using only Fourier Analysis
Scott Aaronson · 2008
Later among the works it cites.
The Probabilistic Method
Noga Alon and Joel Spencer · 2008
Later among the works it cites.
Conditional Inapproximability and Limited Independence
Per Austrin · 2008
Later among the works it cites.
Random graphs and branching processes
Béla Bollobás and Oliver Riordan · 2008
Later among the works it cites.
Short PCPs with polylog query complexity
Eli Ben-Sasson and Madhu Sudan · 2008
Later among the works it cites.
Agnostically learning decision trees
Parikshit Gopalan, Adam Kalai, and Adam Klivans · 2008
Later among the works it cites.
Boolean functions with small spectral norm
Ben Green and Tom Sanders · 2008
Later among the works it cites.
Learning geometric concepts via Gaussian surface area
Adam Klivans, Ryan O’Donnell, and Rocco Servedio · 2008
Later among the works it cites.
Vertex Cover might be hard to approximate to within 2 − ϵ 2-\epsilon
Subhash Khot and Oded Regev · 2008
Later among the works it cites.
Unconditional pseudorandom generators for low degree polynomials
Shachar Lovett · 2008
Later among the works it cites.
Extremal properties of polynomial threshold functions
Ryan O’Donnell and Rocco Servedio · 2008
Later among the works it cites.
An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests
Ryan O’Donnell and Yi Wu · 2008
Later among the works it cites.
Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008
Later among the works it cites.
The randomized decision tree complexity of the recursive majority of three function on 3 n 3^{n} inputs is at least 2.5 n 2.5^{n}
Jonah Sherman · 2008
Later among the works it cites.
The Mathematics of Preference, Choice and Order
Steven Brams, William Gehrlein, and Fred Roberts, editors · 2009
Later among the works it cites.
Constructing small-bias sets from algebraic-geometric codes
Avraham Ben-Aroya and Amnon Ta-Shma · 2009
Later among the works it cites.
Improved approximation of linear threshold functions
Ilias Diakonikolas and Rocco Servedio · 2009
Later among the works it cites.
Explicit lower bound for fooling polynomials by the sum of small-bias generators
Shachar Lovett and Yoav Tzur · 2009
Later among the works it cites.
3-Bit dictator testing: 1 vs. 5/8
Ryan O’Donnell and Yi Wu · 2009
Later among the works it cites.
Approximating NP-hard problems: efficient algorithms and their limits
Prasad Raghavendra · 2009
Later among the works it cites.
Correlation bounds for polynomials over { 0 , 1 } \{0,1\}
Emanuele Viola · 2009
Later among the works it cites.
The sum of d d small-bias generators fools polynomials of degree d d
Emanuele Viola · 2009
Later among the works it cites.
BV functions in abstract Wiener spaces
Luigi Ambrosio, Michele Miranda Jr., Stefania Maniglia, and Diego Pallara · 2010
Later among the works it cites.
Towards sharp inapproximability for any 2 2 -CSP
Per Austrin · 2010
Later among the works it cites.
Polynomial regression under arbitrary product distributions
Eric Blais, Ryan O’Donnell, and Karl Wimmer · 2010
Later among the works it cites.
Boolean functions for cryptography and error-correcting codes
Claude Carlet · 2010
Later among the works it cites.
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco Servedio, and Li-Yang Tan · 2010
Later among the works it cites.
Fooling functions of halfspaces under product distributions
Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman · 2010
Later among the works it cites.
Sets of finite perimeter and the Hausdorff-Gauss measure on the Wiener space
Masanori Hino · 2010
Later among the works it cites.
Bounding the sensitivity of polynomial threshold functions
Prahladh Harsha, Adam Klivans, and Raghu Meka · 2010
Later among the works it cites.
Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry
Subhash Khot · 2010
Later among the works it cites.
On the Unique Games Conjecture
Subhash Khot · 2010
Later among the works it cites.
Breaking the ϵ \epsilon -soundness bound of the linearity test over GF ( 2 ) (2)
Tali Kaufman, Simon Litsyn, and Ning Xie · 2010
Later among the works it cites.
On Hoeffding decomposition in l p l_{p}
Stanisław Kwapień · 2010
Later among the works it cites.
Decision trees and influence: an inductive proof of the OSSS Inequality
Homin Lee · 2010
Later among the works it cites.
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz · 2010
Later among the works it cites.
Testing halfspaces
Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco Servedio · 2010
Later among the works it cites.
Gaussian bounds for noise correlation of functions
Elchanan Mossel · 2010
Later among the works it cites.
Quantitative noise sensitivity and exceptional times for percolation
Oded Schramm and Jeffrey Steif · 2010
Later among the works it cites.
The need for structure in quantum speedups
Scott Aaronson and Andris Ambainis · 2011
Later among the works it cites.
Surface measures and convergence of the Ornstein–Uhlenbeck semigroup in Wiener spaces
Luigi Ambrosio and Alessio Figalli · 2011
Later among the works it cites.
Tight bounds on the average sensitivity of k k -CNF
Kazuyuki Amano · 2011
Later among the works it cites.
Normal approximation by Stein’s method
Louis Chen, Larry Goldstein, and Qi-Man Shao · 2011
Later among the works it cites.
Testing Fourier dimensionality and sparsity
Parikshit Gopalan, Ryan O’Donnell, Rocco Servedio, Amir Shpilka, and Karl Wimmer · 2011
Later among the works it cites.
The influence lower bound via query elimination
Rahul Jain and Shengyu Zhang · 2011
Later among the works it cites.
On Elliptic Curves, the ABC Conjecture, and Polynomial Threshold Functions
Daniel Kane · 2011
Later among the works it cites.
Improved bounds for the randomized decision tree complexity of recursive majority
Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao · 2011
Later among the works it cites.
Small-bias sets from extended norm-trace codes
Gretchen Matthews and Justin Peachey · 2011
Later among the works it cites.
Hypercontractivity, sum-of-squares proofs, and their applications
Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou · 2012
Later among the works it cites.
Majority is Stablest : discrete and SoS
Anindya De, Elchanan Mossel, and Joe Neeman · 2012
Later among the works it cites.
DNF sparsification and a faster deterministic counting algorithm
Parikshit Gopalan, Raghu Meka, and Omer Reingold · 2012
Later among the works it cites.
On the correlation of parity and small-depth circuits
Johan Håstad · 2012
Later among the works it cites.
A structure theorem for Boolean functions with small total influences
Hamed Hatami · 2012
Later among the works it cites.
A satisfiability algorithm for 𝖠𝖢 0 \mathsf{AC}^{0}
Russell Impagliazzo, William Matthews, and Ramamohan Paturi · 2012
Later among the works it cites.
On some extensions of the FKN theorem
Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub Wojtaszczyk · 2012
Later among the works it cites.
The correct exponent for the Gotsman–Linial conjecture
Daniel Kane · 2012
Later among the works it cites.
Gaussian noise sensitivity and Fourier tails
Guy Kindler and Ryan O’Donnell · 2012
Later among the works it cites.
An improved lower bound for the randomized decision tree complexity of recursive majority
Nikos Leonardos · 2012
Later among the works it cites.
Robust optimality of Gaussian noise stability
Elchanan Mossel and Joe Neeman · 2012
Later among the works it cites.
An introduction to BV functions in Wiener spaces
Michele Miranda Jr., Matteo Novaga, and Diego Pallara · 2012
Later among the works it cites.
On reverse hypercontractivity
Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen · 2012
Later among the works it cites.
A new point of NP-hardness for Unique-Games
Ryan O’Donnell and John Wright · 2012
Later among the works it cites.
A cornucopia of Hermite polynomials
Jonas Teuwen · 2012
Later among the works it cites.
Finding correlations in subquadratic time, with applications to learning parities and juntas with noise
Gregory Valiant · 2012
Later among the works it cites.
On sets of finite perimeter in Wiener spaces: reduced boundary and convergence to halfspaces
Luigi Ambrosio, Alessio Figalli, and Eris Runa · 2013
Later among the works it cites.
On sharp thresholds of monotone properties: Bourgain’s proof revisited
Deepak Bal · 2013
Later among the works it cites.
L 1 L^{1} -smoothing for the Ornstein–Uhlenbeck semigroup
Keith Ball, Franck Barthe, Witold Bednorz, Krzysztof Oleszkiewicz, and Paweł Wolff · 2013
Later among the works it cites.
Majority is Stablest : Discrete and SoS
Anindya De, Elchanan Mossel, and Joe Neeman · 2013
Later among the works it cites.
A two-sided estimate for the Gaussian noise stability deficit
Ronen Eldan · 2013
Later among the works it cites.
Remarks on noise sensitivity, Brascamp–Lieb and Slepian inequalities
Michel Ledoux · 2013
Later among the works it cites.
Personal communication to the author, October 2013
Michele Miranda Jr · 2013
Later among the works it cites.
Sharpness of KKL on Schreier graphs
Ryan O’Donnell and Karl Wimmer · 2013
Later among the works it cites.
On the absolute constants in the Berry–Esseen inequality and its structural and nonuniform improvements
Irina Shevtsova · 2013
Later among the works it cites.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Later among the works it cites.
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou · 2016
Later among the works it cites.