New answers tagged fourier-analysis
0
Just posting an answer to close the question.
See the helpful comments to the question which contain all the info;
Yes it is vaccous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much.
Better bounds are known (...
3
$\newcommand{\bm}{\boldsymbol}$The two scenarios are not equal even when $s = t$. In the $s,t$ case you always re-sample the same number of bits, while in the $\delta$ case you get a binomial distribution in the number of bits flipped.
Let us define $\text{Maj}$ in a slightly different way than you might be used to, but assure yourself it is correct.
$$\...
Top 50 recent answers are included
