We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,
our proof does not use the method of higher moments, but rather uses a simple ... more >>>

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any
unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak
(2009) and rigorously establishes the peculiar power of bi-directional streams ... more >>>

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

more >>>