Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>

Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, ... more >>>