We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size ... more >>>