Skip to main content
3 of 3
Spelling in title
Neil Strickland
  • 56.9k
  • 7
  • 142
  • 262

Tail Bound on Binomial

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!