Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Symmetric Logspace:
TR03-077 | 4th September 2003
Till Tantau

Logspace Optimisation Problems and their Approximation Properties

This paper introduces logspace optimisation problems as
analogues of the well-studied polynomial-time optimisation
problems. Similarly to them, logspace
optimisation problems can have vastly different approximation
properties, even though the underlying existence and budget problems
have the same computational complexity. Numerous natural problems
are presented that exhibit such a varying ... more >>>

TR04-094 | 10th November 2004
Omer Reingold

Undirected ST-Connectivity in Log-Space

We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>

ISSN 1433-8092 | Imprint