Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 62 Issue 6, December 2015

Section: Computational Geometry

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled, Benjamin Raichel
Article No.: 44
DOI: 10.1145/2831230

We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTAS's) to several well known problems in Computational Geometry, such as k-center clustering and farthest nearest neighbor....

Section: Cryptography

Attribute-Based Encryption for Circuits
Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee
Article No.: 45
DOI: 10.1145/2824233

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an ℓ-bit public index ind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows decrypting the...

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
Eric Miles, Emanuele Viola
Article No.: 46
DOI: 10.1145/2792978

This article takes a new step towards closing the gap between pseudorandom functions (PRF) and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways,...

Section: Distributed Computing

Simple, Fast and Deterministic Gossip and Rumor Spreading
Bernhard Haeupler
Article No.: 47
DOI: 10.1145/2767126

We study gossip algorithms for the rumor spreading problem, which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as...

Section: Logic in Computer Science

Solving Linear Programs without Breaking Abstractions
Matthew Anderson, Anuj Dawar, Bjarki Holm
Article No.: 48
DOI: 10.1145/2822890

We show that the ellipsoid method for solving linear programs can be implemented in a way that respects the symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or...

Section: Quantum Cryptography

Revocable Quantum Timed-Release Encryption
Dominique Unruh
Article No.: 49
DOI: 10.1145/2817206

Timed-release encryption is a kind of encryption scheme in which a recipient can decrypt only after a specified amount of time T (assuming that we have a moderately precise estimate of his computing power). A revocable timed-release...

Section: Randomized Algorithms and Probabilistic Analysis

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
Andreas Galanis, Daniel Štefankovič, Eric Vigoda
Article No.: 50
DOI: 10.1145/2785964

A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ...

Section: Scientific Computing and High Performance Computing

Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization
Haim Avron, Alex Druinsky, Anshul Gupta
Article No.: 51
DOI: 10.1145/2814566

Asynchronous methods for solving systems of linear equations have been researched since Chazan and Miranker's [1969] pioneering paper on chaotic relaxation. The underlying idea of asynchronous methods is to avoid processor idle time by allowing...