Publications
Sort & Filters
Filters
149 results
149 results
2002
Bender, Michael A., Antonio Fernández, Dana Ron, Amit Sahai, and Salil Vadhan. “The Power of a Pebble: Exploring and Mapping Directed Graphs.”. Information and Computation 176, no. 1 (2002): 1-21.
Bender, Michael A., Antonio Fernández, Dana Ron, Amit Sahai, and Salil Vadhan. “The Power of a Pebble: Exploring and Mapping Directed Graphs.”. Information and Computation 176, no. 1 (2002): 1-21.
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the problem. In this paper, we consider a model that makes...
2001
Vadhan, Salil. “The Complexity of Counting in Sparse, Regular, and Planar Graphs.”. SIAM Journal on Computing 31, no. 2 (2001): 398-427.
Vadhan, Salil. “The Complexity of Counting in Sparse, Regular, and Planar Graphs.”. SIAM Journal on Computing 31, no. 2 (2001): 398-427.
We show that a number of graph-theoretic counting problems remain NP-hard, indeed #P-complete, in very restricted classes of graphs. In particular, we prove that the problems of counting matchings, vertex covers, independent sets, and extremal variants of...
1999
Wallner, D., E. Harder, and R. Agee. “Key Management for Multicast: Issues and Architectures.”. Internet RFC 2627, no. June 1999 (1999).
Wallner, D., E. Harder, and R. Agee. “Key Management for Multicast: Issues and Architectures.”. Internet RFC 2627, no. June 1999 (1999).
This report contains a discussion of the difficult problem of key management for multicast communication sessions. It focuses on two main areas of concern with respect to key management, which are, initializing the multicast group with a common net key...
Sahai, Amit, and Salil Vadhan. “ Manipulating Statistical Difference.”. Randomization Methods in Algorithm Design (DIMACS Workshop, December 1997), Volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43 (1999): 251-70.
Sahai, Amit, and Salil Vadhan. “ Manipulating Statistical Difference.”. Randomization Methods in Algorithm Design (DIMACS Workshop, December 1997), Volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43 (1999): 251-70.
We give several efficient transformations for manipulating the statistical difference (variation distance) between a pair of probability distributions. The effects achieved include increasing the statistical difference, decreasing the statistical...
1998
Goldreich, Oded, Amit Sahai, and Salil Vadhan. “Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.”. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC ‘98), 1998, 399-408.
Goldreich, Oded, Amit Sahai, and Salil Vadhan. “Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.”. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC ‘98), 1998, 399-408.
We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof system which is statistical zero-knowledge with respect to any verifier. This is done by limiting the behavior of...