Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 7 Issue 4, September 2015

Exploring the Subexponential Complexity of Completion Problems
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger
Article No.: 14
DOI: 10.1145/2799640

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the...

Quantum XOR Games
Oded Regev, Thomas Vidick
Article No.: 15
DOI: 10.1145/2799560

We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a...

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly
Oded Goldreich, Or Meir
Article No.: 16
DOI: 10.1145/2799645

An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of NP and MA were introduced in passing by Fortnow, Santhanam, and Williams, who also showed...

On Approximate Decidability of Minimal Programs
Jason Teutsch, Marius Zimand
Article No.: 17
DOI: 10.1145/2799561

An index e in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from e. Since the 1960s, it has been known that, in any reasonable programming language, no effective...