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 efficiently construct a polynomially-bounded min-isolating weight function for any given digraph (or even just for *layered* digraphs), it would follow that NL = UL, thanks to work by Reinhardt and Allender (SICOMP 2000).

Van Melkebeek and Prakriya constructed an explicit, deterministic, min-isolating weight function for layered digraphs (SICOMP 2019). Their weight function is *oblivious*, i.e., it is a single weight function that works for all width-$w$ length-$n$ layered digraphs simultaneously, assigning a weight to each possible edge in the digraph without needing to know which edges are actually present. However, they use weights of magnitude $M = 2^{\Theta(\log n \cdot \log w)}$ instead of the desired $M = \mathrm{poly}(wn)$.

In this work, we prove that every deterministic, oblivious weight function that is min-isolating for width-$w$ length-$n$ layered digraphs must use weights of magnitude $2^{\Omega(\log w \cdot \log n)}$. This rules out one possible method of proving NL = UL. Our proof is based on a connection with coding theory. A *solid burst error* is a vector $e \in \mathbb{Z}_q^n$ such that the support of $e$ is an interval. Using spectral graph theory methods, we prove that every code $\mathcal{C} \subseteq \mathbb{Z}_q^n$ that can detect solid burst errors with Hamming weight up to $d$ must satisfy $|\mathcal{C}| \leq q^{n - \Omega(\log d)}$, which is optimal. The best prior bound, by Das (BEEI 2012), says $|\mathcal{C}| \leq q^n / (d + 1)$ assuming the code is linear.