Testing whether a bounded-degree $n$-vertex graph is bipartite or far from bipartite requires $\widetilde\Theta(\sqrt n)$ queries (Goldreich--Ron, Combinatorica'99, Algorithmica'02). An interactive proof of proximity (IPP) is a hybrid model of property testing and interactive proofs: the verifier faces the same task with the same query access, but it now interacts ... more >>>

We prove that every language in $\mathrm{P}^{\# \mathrm{P}}$ can be decided by a bounded-error randomized algorithm that uses only $O(\log n)$ bits of work space. The algorithm is guaranteed to halt for every input and every setting of the random tape. However, there is a catch: the algorithm uses a ... more >>>

We construct an explicit hitting set generator (HSG) for ordered read-once branching programs of width 4. For every length $n$ and every $\varepsilon \in (0,1)$, every width-4 length-$n$ program that accepts more than an $\varepsilon$ fraction of its inputs accepts at least one output of the generator, and the seed ... more >>>