enter search term and/or author name
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled, Benjamin Raichel
Article No.: 44
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....
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
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,...
Simple, Fast and Deterministic Gossip and Rumor Spreading
Article No.: 47
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...
Solving Linear Programs without Breaking Abstractions
Matthew Anderson, Anuj Dawar, Bjarki Holm
Article No.: 48
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...
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...
Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
Andreas Galanis, Daniel Štefankovič, Eric Vigoda
Article No.: 50
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 Δ...
Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization
Haim Avron, Alex Druinsky, Anshul Gupta
Article No.: 51
Asynchronous methods for solving systems of linear equations have been researched since Chazan and Miranker's  pioneering paper on chaotic relaxation. The underlying idea of asynchronous methods is to avoid processor idle time by allowing...