Open Problems in Analysis of Boolean Functions

Abstract

A list of open problems in the field of analysis of boolean functions, compiled February 2012 for the Simons Symposium.

27 problems

References in corpus (4)

• On the Bogolyubov-Ruzsa lemma
• The Need for Structure in Quantum Speedups
• Green's sumset problem at density one half
• A Small PRG for Polynomial Threshold Functions of Gaussians

Cited by in corpus (5)

• DNF Sparsification and a Faster Deterministic Counting Algorithm
• On the sum of the L1 influences of bounded functions
• On the Sum of Linear Coefficients of a Boolean Valued Function
• Algorithms for Similarity Search and Pseudorandomness
• Optimal Boolean Locality-Sensitive Hashing