New answers tagged boolean-functions
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.
- 1
4
votes
Accepted
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 ...
- 632
Top 50 recent answers are included