Articles under category:
Boolean Functions
ToC Library Graduate Surveys 1 (2008) 20 pages
A Brief Introduction to Fourier Analysis on the Boolean Cube
by Ronald de Wolf
Vol 17, Article 7 (pp 1-46) [APRX-RND19 Spec Issue]
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
Vol 16, Article 9 (pp 1-12)
On the Complexity of Computing a Random Boolean Function Over the Reals
by Pavel Hrubeš
Vol 15, Article 12 (pp 1-24)
Outlaw Distributions and Locally Decodable Codes
by Jop Briët, Zeev Dvir, and Sivakanth Gopi
Vol 15, Article 11 (pp 1-13)
Fourier Sparsity and Dimension
by Swagato Sanyal
Vol 15, Article 1 (pp 1-55)
Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions
by Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer
Vol 13, Article 7 (pp 1-18)
A Communication Game Related to the Sensitivity Conjecture
by Justin Gilmer, Michal Koucký, and Michael Saks
Vol 12, Article 4 (pp 1-50)
Majority is Stablest: Discrete and SoS
by Anindya De, Elchanan Mossel, and Joe Neeman
Vol 11, Article 16 (pp 403-412) [NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 10, Article 3 (pp 55-75) [Boolean Spec Issue]
Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube
by Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman
Vol 10, Article 2 (pp 27-53)
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
Vol 9, Article 29 (pp 889-896) [NOTE] [Boolean Spec Issue]
Hypercontractivity Via the Entropy Method
by Eric Blais and Li-Yang Tan
Vol 9, Article 23 (pp 703-757) [APRX-RND12 Spec Issue]
Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
by Cenny Wenner
Vol 9, Article 20 (pp 653-663)
Approximating the AND-OR Tree
by Alexander A. Sherstov
Vol 9, Article 18 (pp 593-615) [Boolean Spec Issue]
Making Polynomials Robust to Noise
by Alexander A. Sherstov
Vol 9, Article 17 (pp 587-592) [NOTE] [Boolean Spec Issue]
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
Vol 7, Article 11 (pp 155-176)
Distribution-Free Testing for Monomials with a Sublinear Number of Queries
by Elya Dolev and Dana Ron
Vol 7, Article 10 (pp 147-153) [NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
Vol 7, Article 6 (pp 75-99)
Testing Linear-Invariant Non-Linear Properties
by Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie
Vol 7, Article 4 (pp 45-48) [NOTE]
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
Vol 6, Article 4 (pp 81-84) [NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
Vol 5, Article 13 (pp 257-282)
Optimal Cryptographic Hardness of Learning Monotone Functions
by Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, and Hoeteck Wee
Vol 5, Article 10 (pp 191-216)
Distribution-Free Testing Lower Bound for Basic Boolean Functions
by Dana Glasner and Rocco A. Servedio