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 >>>

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$.
Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have:
$$
agree(F,L) ... more >>>