Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with space complexity:
TR95-005 | 1st January 1995
Maciej Liskiewicz, Rüdiger Reischuk

The Sublogarithmic Alternating Space World

This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>

TR96-048 | 12th September 1996
Eric Allender, Klaus-Joern Lange

StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

We present a deterministic algorithm running in space
O((log^2 n)/loglog n) solving the connectivity problem
on strongly unambiguous graphs. In addition, we present
an O(log n) time-bounded algorithm for this problem
running on a parallel pointer machine.

more >>>

TR99-040 | 20th October 1999
Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

Space Complexity in Propositional Calculus

We study space complexity in the framework of
propositional proofs. We consider a natural model analogous to
Turing machines with a read-only input tape, and such
popular propositional proof systems as Resolution, Polynomial
Calculus and Frege systems. We propose two different space measures,
corresponding to the maximal number of bits, ... more >>>

TR02-021 | 11th April 2002
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Space Efficient Algorithms for Directed Series-Parallel Graphs

The subclass of directed series-parallel graphs plays an important role in
computer science. Whether a given graph is series-parallel is a
well studied problem in algorithmic graph theory, for which fast sequential and
parallel algorithms have been developed in a sequence of papers.
Also methods are known to solve ... more >>>

TR04-114 | 21st November 2004
Vladimir Trifonov

An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity

We present a deterministic O(log n log log n) space algorithm for
undirected s,t-connectivity. It is based on the deterministic EREW
algorithm of Chong and Lam (SODA 93) and uses the universal
exploration sequences for trees constructed by Kouck\'y (CCC 01).
Our result improves the O(log^{4/3} n) bound of Armoni ... more >>>

TR05-042 | 15th April 2005
Lance Fortnow, Adam Klivans

Linear Advice for Randomized Logarithmic Space

Revisions: 1

We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.

more >>>

TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>

TR12-185 | 29th December 2012
Siu Man Chan, Aaron Potechin

Tight Bounds for Monotone Switching Networks via Fourier Analysis

We prove tight size bounds on monotone switching networks for the NP-complete problem of
$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for
the P-complete problem of generation. This gives alternative proofs of the separations of m-NC
from m-P and of m-NC$^i$ from ... more >>>

TR13-042 | 25th March 2013
Siu Man Chan

Just a Pebble Game

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>

TR13-093 | 21st June 2013
Anna Gal, Jing-Tang Jang

A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for ... more >>>

TR14-180 | 22nd December 2014
Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Space-Efficient Approximations for Subset Sum

SUBSET SUM is a well known NP-complete problem:
given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ... more >>>

TR15-135 | 19th August 2015
Arnab Bhattacharyya, Palash Dey

Fishing out Winners from Vote Streams

Revisions: 1

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined ... more >>>

TR16-097 | 15th June 2016
Vivek Anand T Kallampally, Raghunath Tewari

Trading Determinism for Time in Space Bounded Computations

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.
... more >>>

TR17-116 | 5th July 2017
Michal Moshkovitz, Dana Moshkovitz

Mixing Implies Strong Lower Bounds for Space Bounded Learning

With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses ... more >>>

TR18-106 | 30th May 2018
Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices
$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous
logarithmic space.

more >>>

TR21-054 | 14th April 2021
James Cook, Ian Mertz

Encodings and the Tree Evaluation Problem

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>

ISSN 1433-8092 | Imprint