Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 10 Issue 2, May 2018

The Weakness of CTC Qubits and the Power of Approximate Counting
Ryan O'Donnell, A. C. Cem Say
Article No.: 5
DOI: 10.1145/3196832

We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of...

Tight Running Time Lower Bounds for Vertex Deletion Problems
Christian Komusiewicz
Article No.: 6
DOI: 10.1145/3186589

For a graph class Π, the Π-Vertex Deletion problem has as input an undirected graph G = (V,E) and an integer k and asks whether there is a set of at most k vertices that can be...

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
Jack H. Lutz, Neil Lutz
Article No.: 7
DOI: 10.1145/3201783

We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of...

Ground State Connectivity of Local Hamiltonians
Sevag Gharibian, Jamie Sikora
Article No.: 8
DOI: 10.1145/3186587

The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this article, we take a new direction by introducing the physically motivated notion of “ground state...

Hardness of Approximation for H-free Edge Modification Problems
Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
Article No.: 9
DOI: 10.1145/3196834

The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free—that is, not...