Articles under category:
Boolean Functions
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 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 |