enter search term and/or author name
Amit Sahai, Cynthia Dwork, Moni Naor
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
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
Alan Demers, Jon Kleinberg, David Kempe
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
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
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
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...