New answers tagged

0 votes

Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

Here is a direct construction: $$F = \left\{S:|\hat{f}(S)|\ge \frac{\epsilon}{\hat{\|}f\hat{\|}_1}\right\}$$ And you can verify the two conditions.
usercfp's user avatar
4 votes

Intuition on Lupanov's Upper Bound on Circuit Size

Yes, there is a simpler construction, essentially due to Shannon. For every $k$, all $2^{2^k}$ functions on $k$ variables can implemented by a circuit of size $2^{2^k}$ (just take some implementation ...
Vladimir Lysikov's user avatar

Top 50 recent answers are included