Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 5 Issue 4, November 2013

Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
Article No.: 13
DOI: 10.1145/2540088

We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of...

Explicit Optimal Hardness via Gaussian Stability Results
Anindya De, Elchanan Mossel
Article No.: 14
DOI: 10.1145/2505766

The results of Raghavendra [2008] show that assuming Khot’s Unique Games Conjecture [2002], for every constraint satisfaction problem there exists a generic semidefinite program that achieves the optimal approximation factor. This result is...

Robust Satisfiability for CSPs: Hardness and Algorithmic Results
Víctor Dalmau, Andrei Krokhin
Article No.: 15
DOI: 10.1145/2540090

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such...

Distortion is Fixed Parameter Tractable
Michael Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances Rosamond, Saket Saurabh
Article No.: 16
DOI: 10.1145/2489789

We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortest path metric of an...

Real Advantage
Alexander Razborov, Emanuele Viola
Article No.: 17
DOI: 10.1145/2540089

We highlight the challenge of proving correlation bounds between boolean functions and real-valued polynomials, where any non-boolean output counts against correlation.

We prove that real-valued polynomials of degree 1 2 lg2...

Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
Ryan C. Harkins, John M. Hitchcock
Article No.: 18
DOI: 10.1145/2539126.2539130

This article extends and improves the work of Fortnow and Klivans [2009], who showed that if a circuit class C has an efficient learning algorithm in Angluin’s model of exact learning via equivalence and membership queries [Angluin 1988],...