Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

We prove that the set disjointness problem has randomized communication complexity
$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement
on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>>