Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Unique Reachability:
TR16-155 | 10th October 2016
Vaibhav Krishan, Nutan Limaye

Isolation Lemma for Directed Reachability and NL vs. L

In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>>

ISSN 1433-8092 | Imprint