All reports by Author Gautam Prakriya:

__
TR17-052
| 19th March 2017
__

Dieter van Melkebeek, Gautam Prakriya#### Derandomizing Isolation in Space-Bounded Settings

__
TR11-009
| 21st January 2011
__

Samir Datta, Gautam Prakriya#### Planarity Testing Revisited

Dieter van Melkebeek, Gautam Prakriya

We study the possibility of deterministic and randomness-efficient isolation in space-bounded 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 NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

Samir Datta, Gautam Prakriya

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.

The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ...
more >>>