Maciej Liskiewicz, Rüdiger Reischuk

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 >>>

Eric Allender, Klaus-Joern Lange

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.

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

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 >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

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 >>>

Vladimir Trifonov

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 >>>

Lance Fortnow, Adam Klivans

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.

Oded Goldreich

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 >>>

Siu Man Chan, Aaron Potechin

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 >>>

Siu Man Chan

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 >>>

Anna Gal, Jing-Tang Jang

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 >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

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 >>>

Arnab Bhattacharyya, Palash Dey

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 >>>

Vivek Anand T Kallampally, Raghunath Tewari

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 >>>

Michal Moshkovitz, Dana Moshkovitz

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 >>>

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

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.

James Cook, Ian Mertz

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 >>>Henning Fernau, Kshitij Gajjar

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider ... more >>>

William Hoza

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

James Cook, Ian Mertz

The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of $\Omega(\log^2 n)$ are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>>