New answers tagged

0 votes

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

Hint: find a random variable $X=X(S)$ such that $\mathbf{E}[X]=\hat{||}f\hat{||}_1$ where the expectation is under the spectral sample. Use this to apply Markov to find an appropriate set with Fourier ...
1 vote

If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

Observe that if a $k$-CNF $\Phi$ is equivalent to an $l$-DNF $\Psi$, then every term of $\Psi$ implies every clause of $\Phi$, i.e., they share a literal. If the Boolean function is not constant, pick ...

Top 50 recent answers are included