Skip to main content

Theory of Computing Systems OnlineFirst articles


Guest Editorial: Special Issue on Algorithmic Game Theory


Guest Editorial: Special Issue on Database Theory


Connecting Knowledge Compilation Classes Width Parameters

The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings …


The Operator Approach to Entropy Games

Entropy games and matrix multiplication games have been recently introduced by Asarin et al. They model the situation in which one player (Despot) wishes to minimize the growth rate of a matrix product, whereas the other player (Tribune) wishes to …

30.05.2019 Open Access

New Bounds for Truthful Scheduling on Two Unrelated Selfish Machines

We consider the minimum makespan problem for n tasks and two unrelated parallel selfish machines. Let Rn be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient algorithms known for …

Aktuelle Ausgaben

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

Weitere Informationen

Premium Partner