Skip to main content

Theory of Computing Systems OnlineFirst articles


Enumeration Complexity of Conjunctive Queries with Functional Dependencies

We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples with a constant delay in between, following a linear-time …


Quadratically Tight Relations for Randomized Query Complexity

In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity …


Grammar-Based Compression of Unranked Trees

We introduce forest straight-line programs (FSLPs for short) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the …


Lower Bound Techniques for QBF Expansion

We propose some general techniques for proving lower bounds in expansion-based QBF proof systems. We present them in a framework centred on natural properties of winning strategies in the ‘evaluation game’ interpretation of QBF semantics. As …


Profit Maximization in Flex-Grid All-Optical Networks

All-optical networks have been largely investigated due to their high data transmission rates. The key to the high speeds in all-optical networks is to maintain the signal in optical form, to avoid the overhead of conversion to and from electrical …

Current Publications

About this journal

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.

Additional information

Premium Partner

    Image Credits