Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-039 | 12th March 2019 06:11

Planarity, Exclusivity, and Unambiguity



We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds on the complexity of several other computational problems on planar graphs. All of these problems are shown to be solvable in logarithmic time on a concurrent-read exclusive-write (CREW) PRAM. The new upper bounds are provided by making use of a known characterization of CREW algorithms in terms of "unambiguous" AC$^1$ circuits. This seems to be the first occasion where this characterization has been used in order to provide new upper bounds on natural problems.


Comment #1 to TR19-039 | 25th June 2019 09:30

We retract Theorem 2 and its corollaries.

Authors: Eric Allender, Archit Chauhan, Samir Datta
Accepted on: 25th June 2019 09:30


The proof of Theorem 2 has a serious flaw that we are unable to resolve. In particular, the statement that our inductive definition translates directly into unambiguous gates is incorrect. A revision will be posted at a later date.

ISSN 1433-8092 | Imprint