- Authors: D. van Melkebeek and G. Prakriya
- Reference:
*SIAM Journal on Computing*, 48: 979-1021, 2019. - Earlier versions:
- D. van Melkebeek and G. Prakriya.
Derandomizing Isolation in Space-Bounded Settings.
In
*Proceedings of the 32nd Computational Complexity Conference*, pages 17:1-33, 2017. - D. van Melkebeek and G. Prakriya. Derandomizing Isolation in Space-Bounded Settings. Electronic Colloquium on Computational Complexity, Technical Report ECCC-TR 17-052, 2017.

- D. van Melkebeek and G. Prakriya.
Derandomizing Isolation in Space-Bounded Settings.
In

A common approach employs small weight assignments that make the
solution of minimum weight unique. The Isolation Lemma and other known
procedures use Ω(*n*) random bits to generate weights of
individual bitlength O(log *n*). We develop a derandomized version
for both settings that uses O((log *n*)^{3/2}) random bits and
produces weights of bitlength O((log *n*)^{3/2})
in logarithmic
space. The construction allows us to show that every language in
NL can be accepted by a nondeterministic machine that runs in
polynomial time and O((log *n*)^{3/2}) space, and has at most one
accepting computation path on every input. Similarly, every language
in LogCFL can be accepted by a nondeterministic machine equipped
with a stack that does not count towards the space bound, that runs in
polynomial time and O((log *n*)^{3/2}) space, and has at most one
accepting computation path on every input.

We also show that the existence of somewhat more restricted isolations for reachability on digraphs implies that NL can be decided in logspace with polynomial advice. A similar result holds for certifying acceptance on shallow semi-unbounded circuits and LogCFL.

dieter@cs.wisc.edu