All reports by Author Kewen Wu:

__
TR21-046
| 22nd March 2021
__

Uma Girish, Avishay Tal, Kewen Wu#### Fourier Growth of Parity Decision Trees

__
TR19-137
| 24th September 2019
__

Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Decision list compression by mild random restrictions

Revisions: 1

__
TR19-110
| 23rd August 2019
__

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Improved bounds for the sunflower lemma

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>

Shachar Lovett, Kewen Wu, Jiapeng Zhang

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

A sunflower with $r$ petals is a collection of $r$ sets so that the

intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ...
more >>>