Skip to main content
2 of 3
TeX
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

Tail Bound on Bionimal

Context: circuit complexity argument:

How do I show that $$\sum_{i=0}^{n/2- \sqrt{n}} {n \choose i} \geq 2^n/50$$ ? (as n goes to infinity)

[This shows up in proving Mod2 is not in ACC(3)].

Standard approach would be to use chernoff bounds; but it provides the wrong direction.

Thanks!