16 citations · 22 across the 7 of their papers we have counts for
8 papers
An inequality for the Fourier spectrum of parity decision trees
Eric Blais, Li-Yang Tan, Andrew Wan
We give a new bound on the sum of the linear Fourier coefficients of a Boolean function in terms of its parity decision tree complexity. This result generalizes an inequality of O'…
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Thomas Steinke, Salil Vadhan, Andrew Wan
We present an explicit pseudorandom generator for oblivious, read-once, width- branching programs, which can read their input bits in any order. The generator has seed length $\…
Approximate resilience, monotonicity, and the complexity of agnostic learning
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan +2
A function is -resilient if all its Fourier coefficients of degree at most are zero, i.e., is uncorrelated with all low-degree parities. We study the notion of $\mat…
Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
Andrew Wan, John Wright, Chenggang Wu
Given , define the \emph{spectral distribution} of to be the distribution on subsets of in which the set is sampled with probabil…
Satisfiability and Evolution
Adi Livnat, Christos Papadimitriou, Aviad Rubinstein +2
We show that, if truth assignments on variables reproduce through recombination so that satisfaction of a particular Boolean function confers a small evolutionary advantage, th…
On the Distribution of the Fourier Spectrum of Halfspaces
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio +2
Bourgain showed that any noise stable Boolean function can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's resul…