Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 51 Issue 6, November 2004

Concurrent zero-knowledge
Cynthia Dwork, Moni Naor, Amit Sahai
Pages: 851-898
DOI: 10.1145/1039488.1039489
Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto. In this article, we study the problem of maintaining zero-knowledge.We introduce the...

New lattice-based cryptographic constructions
Oded Regev
Pages: 899-942
DOI: 10.1145/1039488.1039490
We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two...

Spatial gossip and resource location protocols
David Kempe, Jon Kleinberg, Alan Demers
Pages: 943-967
DOI: 10.1145/1039488.1039491
The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes...

A new approach to dynamic all pairs shortest paths
Camil Demetrescu, Giuseppe F. Italiano
Pages: 968-992
DOI: 10.1145/1039488.1039492
We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued...

Compact oracles for reachability and approximate distances in planar digraphs
Mikkel Thorup
Pages: 993-1024
DOI: 10.1145/1039488.1039493
It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each...

Fast monte-carlo algorithms for finding low-rank approximations
Alan Frieze, Ravi Kannan, Santosh Vempala
Pages: 1025-1041
DOI: 10.1145/1039488.1039494
We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the...