We describe a method that lifts an arbitrary polynomial $f$ with sparsity $s$ to a polynomial that requires a read-once oblivious algebraic program of width $s$ for every variable order. To do so, we introduce a technique for constructing a gadget based on erasure codes over finite fields, where each ... more >>>

For a directed graph $G = (V, E)$, we say that a weight function $\rho \colon E \to [M]$ is *min-isolating* if the minimum-weight path from $u$ to $v$ is unique for each pair of vertices $u, v \in V$ such that $v$ is reachable from $u$. If we could ... more >>>

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length
$$
O\left((\log w+\log(1/\varepsilon))\cdot \log n\right).
$$
This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the ... more >>>