Abstract
We study the possibility of deterministic and randomnessefficient isolation in spacebounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NLcomplete problem of reachability on digraphs, and for the LogCFLcomplete problem of certifying acceptance on shallow semiunbounded circuits.
A common approach employs small weight assignments that make the solution of minimum weight unique. The Isolation Lemma and other known procedures use Omega(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 semiunbounded circuits and LogCFL.
BibTeX  Entry
@InProceedings{vanmelkebeek_et_al:LIPIcs:2017:7529,
author = {Dieter van Melkebeek and Gautam Prakriya},
title = {{Derandomizing Isolation in SpaceBounded Settings}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {5:15:32},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7529},
URN = {urn:nbn:de:0030drops75297},
doi = {10.4230/LIPIcs.CCC.2017.5},
annote = {Keywords: Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification}
}
Keywords: 

Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification 
Seminar: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

21.07.2017 