ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > NL:
Reports tagged with NL:
TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1 , Comments: 1

The aim of this paper is to use formal power series techniques to
study the structure of small arithmetic complexity classes such as
GapNC^1 and GapL. More precisely, we apply the Kleene closure of
languages and the formal power series operations of inversion and
root ... more >>>


TR09-024 | 26th February 2009
Raghav Kulkarni

On the Power of Isolation in Planar Structures

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>




ISSN 1433-8092 | Imprint