Skip to main content

Theory of Computing Systems OnlineFirst articles

30.06.2020 Open Access

On the Average Case of MergeInsertion

MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the …


Consistent Query Answering for Primary Keys in Datalog

We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query …


Belga B-Trees

We revisitself-adjustingexternal memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts …


Forward Looking Huffman Coding

Huffman coding is known to be optimal, yet its dynamic version may yield smaller compressed files. The best known bound is that the number of bits used by dynamic Huffman coding in order to encode a message of n characters is at most larger by n …


Dichotomy for Holant∗ Problems on the Boolean Domain

Holant problems are a general framework to study counting problems. Both counting constraint satisfaction problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant∗(F)$\text {Holant}^{*}(\mathcal …

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