Skip to main content

Theory of Computing Systems OnlineFirst articles

13-11-2020 Open Access

On the Complexity of the Smallest Grammar Problem over Fixed Alphabets

In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is …


Computability of Products of Chainable Continua

We examine conditions under which a semicomputable set in a computable topological space is computable. In particular, we examine topological pairs (A, B) with the following property: if X is a computable topological space and f : A → X …

12-11-2020 Open Access

Streaming Algorithms for Bin Packing and Vector Scheduling

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but …


Index-based, High-dimensional, Cosine Threshold Querying with Optimality Guarantees

Given a database of vectors, a cosine threshold query returns all vectors in the database having cosine similarity to a query vector above a given threshold θ. These queries arise naturally in many applications, such as document retrieval, image …


Faster Parameterized Algorithm for Cluster Vertex Deletion

In the Cluster Vertex Deletion problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a graph in which every …

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