Deterministic, Oblivious Isolation for Space-Bounded Computation Requires Large Weights

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 $\mathsf{NL} = \mathsf{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 $\mathsf{NL} = \mathsf{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.

A "nondeterministic algorithm" uses guesswork to try to prove some statement. If the algorithm outputs "yes" at the end, it means the statement is true, whereas if the algorithm outputs "no," it could mean the statement is false, or it could just mean that the algorithm made a poor sequence of guesses. We say that a nondeterministic algorithm is "unambiguous" if there is always at most one sequence of guesses that leads the algorithm to output "yes." There is a conjecture in complexity theory, called the "$\mathsf{NL} = \mathsf{UL}$" conjecture, which says that every nondeterministic algorithm can be converted into an unambiguous algorithm without significantly increasing the amount of memory that the algorithm uses. In this paper, we rule out one method of proving $\mathsf{NL} = \mathsf{UL}$.