Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 6 Issue 1, March 2014

The Hardness of Being Private
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
Article No.: 1
DOI: 10.1145/2567671

Kushilevitz [1989] initiated the study of information-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable [Kushilevitz 1989, Brandt and...

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan O’Donnell, Li-Yang Tan, John Wright
Article No.: 2
DOI: 10.1145/2537800

We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with (16/17 + &egr;) of the edges bichromatic. In a related result, we show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a...

Unions of Disjoint NP-Complete Sets
Christian Glaßer, John M. Hitchcock, A. Pavan, Stephan Travers
Article No.: 3
DOI: 10.1145/2591508

We study the following question: if A and B are disjoint NP-complete sets, then is AB NP-complete? We provide necessary and sufficient conditions under which the union of disjoint NP-complete sets remain...

On Effective Convergence of Numerical Solutions for Differential Equations
Shu-Ming Sun, Ning Zhong
Article No.: 4
DOI: 10.1145/2578219

This article studies the effective convergence of numerical solutions of initial value problems (IVPs) for ordinary differential equations (ODEs). A convergent sequence {Ym} of numerical solutions is said to be effectively...

Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
Ryan O’Donnell, Yi Wu, Yuan Zhou
Article No.: 5
DOI: 10.1145/2578221

We study lower bounds for Locality-Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}d under the Hamming distance. Recall that H is said to be an (r, cr, p, q)-sensitive hash family if all...