Skip to main content

Theory of Computing Systems OnlineFirst articles

Open Access 23.11.2022

Characterizations and Directed Path-Width of Sequence Digraphs

Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph G = (V,A) by a number k of sequences with entries from …


Polynomially Ambiguous Unary Weighted Automata over Fields

Every univariate rational series over an algebraically closed field is shown to be realised by some polynomially ambiguous unary weighted automaton. Unary weighted automata over algebraically closed fields thus always admit polynomially ambiguous …

Open Access 04.11.2022

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in Quasi - NP = NTIME [ n ( log n ) O ( 1 ) ] $\mathsf {Quasi}\text …


The Complexity of Grid Coloring

A c-coloring of the grid GN,M = [N] × [M] is a mapping of GN,M into [c] such that no four corners forming a rectangle have the same color. In 2009 a challenge was proposed to find a 4-coloring of G17,17. Though a coloring was produced, finding it …


Ergodic Theorems and Converses for PSPACE Functions

We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow (Krengel Monatshefte Für Mathematik 86, 3–6 1978). In …

Über diese Zeitschrift

Statement of Scope

TOCS is devoted to publishing original research from all areas of theoretical computer science, ranging from foundational areas such as computational complexity, to fundamental areas such as algorithms and data structures, to focused areas such as parallel and distributed algorithms and architectures.

Theory of Computing Systems
Jahrgang 30/1997 - Jahrgang 66/2022
Springer US
Elektronische ISSN
Print ISSN

Premium Partner