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
A Brief Introduction to Fourier Analysis on the Boolean Cube
by Ronald de Wolf
Vol 20, Article 4 (pp 1-13)
[Boolean Spec Issue]
Influential Coalitions for Boolean Functions I: Constructions
by Jean Bourgain, Jeff Kahn, and Gil Kalai
Influential Coalitions for Boolean Functions I: Constructions
by Jean Bourgain, Jeff Kahn, and Gil Kalai
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
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š
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
Outlaw Distributions and Locally Decodable Codes
by Jop Briët, Zeev Dvir, and Sivakanth Gopi
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
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
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
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
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
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
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
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
Circumventing $d$-to-1ドル$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
by Cenny Wenner
Vol 9, Article 18 (pp 593-615)
[Boolean Spec Issue]
Making Polynomials Robust to Noise
by Alexander A. Sherstov
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
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
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
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
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
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
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
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
Distribution-Free Testing Lower Bound for Basic Boolean Functions
by Dana Glasner and Rocco A. Servedio