Improvement of Chernoff bound in Binomial case We know from Chernoff bound
$P\bigg(X \leq (\frac{1}{2}-\epsilon)N\bigg)\leq e^{-2\epsilon^2 N}$ where 
$X$ follows Binomial($N, \frac{1}{2}$). 
If I take $N=1000, \epsilon=0.01$, the upper bound is 0.82. 
However, the actual value is 0.27. Can we improve this Chernoff bound? 
 A: An explicit high-accuracy bound on the Kolmogorov distance between a properly standardized binomial distribution $B(N,p)$ and the standard normal distribution is provided by the theorem on page 129 of Uspensky's book "Introduction to Mathematical Probability" (1937). In your case, of $p=1/2$, this theorem implies that for any integer $x$ and any natural $N\ge100$
\begin{equation}
 |P(X\le x)-\Phi(z)|<\delta:=\frac{0.52}N+\exp(-\tfrac34\,\sqrt N),
\end{equation}
where $\Phi$ is the standard normal cumulative distribution function and $z:=(x-Np+1/2)/\sqrt{N/4}$. In particular, for your $N=1000$, we have $\delta=0.000520000050\ldots<\frac1{1923}$. So, for $N=1000, \epsilon=0.01$, Uspensky's result implies that the true probability (which is $0.27398\ldots$) is in the interval $[0.27397\ldots-\frac1{1923},0.27397\ldots+\frac1{1923}]\subset[0.27345, 0.27450]$, which is much more informative than 
the Chernoff and entropy upper bounds on $0.27398\ldots$, which both are $\approx0.82$. 
As was commented by user RaphaelB4, the Chernoff and entropy upper bounds are bounds on probabilities of large deviations. Those probabilities are small, in contrast with your probability $0.27398\ldots$, which makes large deviation bounds unsuitable in your example. Also, there are large deviation bounds much better than Chernoff's. E.g., in a more general situation one has an upper bound on large deviation probabilities that is asymptotic to the corresponding Gaussian tail.  
A: One can obtain a slight improvment using an entropy bound. It is well known that
$$\sum_{i \le m} \binom{N}{i} \le 2^{N \cdot H(m/N)},$$
where $m\le N/2$ and $H$ is the binary entropy function. Thus,
$$P(X \le (\frac{1}{2}-\epsilon)N) = 2^{-N}\sum_{i \le (\frac{1}{2}-\varepsilon)N} \binom{N}{i} \le 2^{N(-1+H(\frac{1}{2}-\epsilon))}.$$
This is always superior to the Chernoff bound. In fact, a Taylor expansion of $H$ around $\frac{1}{2}$ shows that
$$H(\frac{1}{2}-\epsilon)=1-\frac{1}{2\log 2} \sum_{n \ge 1}\frac{(2\epsilon)^{2n}}{n(2n-1)},$$
so that
$$ P(X \le (\frac{1}{2}-\epsilon)N) \le e^{-N(2\epsilon^2 +\sum_{n \ge 2}\frac{(2\epsilon)^{2n}}{2n(2n-1)})}.$$
For you numbers ($N=10^3, p=10^{-2}$), I get 0.818...
A: Section 1.3 of the book Random Graphs by Bela Bollobas gives tighter bounds on tail probabilities of the binomial distribution by using the normal distribution. For instance, the top of page 12 discusses the entropy bound Ofir mentioned. Theorems 1.6-1.7 on pages 13-14 go further, using the DeMoivre-Laplace theorem. The probability you are looking at is approximately $\frac{1}{x \sqrt{2\pi}} e^{-x^2/2}$ where $x = \epsilon N / \sqrt{.25 N}$. Bollobas then says 

the best bounds to date (which are essentially best possible) are due to Littlewood (1969), whose paper is highly recommended

Sounds like it would be a good exercise to see what the Littlewood bound says in your case. The reference is "On the probability in the tail of a binomial distribution", Adv. Appl. Probab. 1, 43-72
A: Actually the Littlewood bound had an error which was corrected by McKay:
Brendan D. McKay, On Littlewood's Estimate for the Binomial Distribution, Advances in Applied Probability, Vol. 21, No. 2 (Jun., 1989), pp. 475-478.
