A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous
best running time bound of $O^*(2^{O(k^2/\log
k)})$.

more >>>

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.
As an ... more >>>