2009 | ||
---|---|---|
112 | EE | Yevgeniy Dodis, Salil P. Vadhan, Daniel Wichs: Proofs of Retrievability via Hardness Amplification. TCC 2009: 109-127 |
111 | EE | Shien Jin Ong, David C. Parkes, Alon Rosen, Salil P. Vadhan: Fairness with an Honest Minority and a Rational Majority. TCC 2009: 36-53 |
2008 | ||
110 | EE | Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan: The Complexity of Distinguishing Markov Random Fields. APPROX-RANDOM 2008: 331-342 |
109 | EE | Kai-Min Chung, Salil P. Vadhan: Tight Bounds for Hashing Block Sources. APPROX-RANDOM 2008: 357-370 |
108 | EE | Dan Gutfreund, Salil P. Vadhan: Limitations of Hardness vs. Randomness under Uniform Reductions. APPROX-RANDOM 2008: 469-482 |
107 | EE | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Dense Subsets of Pseudorandom Sets. FOCS 2008: 76-85 |
106 | EE | Michael Mitzenmacher, Salil P. Vadhan: Why simple hash functions work: exploiting the entropy in a data stream. SODA 2008: 746-755 |
105 | EE | Shien Jin Ong, Salil P. Vadhan: An Equivalence Between Zero Knowledge and Commitments. TCC 2008: 482-500 |
104 | EE | André Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, Salil P. Vadhan: Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model. TCC 2008: 501-534 |
103 | EE | Kai-Min Chung, Salil P. Vadhan: Tight Bounds for Hashing Block Sources CoRR abs/0806.1948: (2008) |
102 | EE | Dan Gutfreund, Salil P. Vadhan: Limitations of Hardness vs. Randomness under Uniform Reductions. Electronic Colloquium on Computational Complexity (ECCC) 15(007): (2008) |
101 | EE | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Dense Subsets of Pseudorandom Sets. Electronic Colloquium on Computational Complexity (ECCC) 15(045): (2008) |
100 | EE | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Electronic Colloquium on Computational Complexity (ECCC) 15(103): (2008) |
99 | EE | Minh-Huyen Nguyen, Salil P. Vadhan: Simpler Session-Key Generation from Short Random Passwords. J. Cryptology 21(1): 52-96 (2008) |
98 | EE | Saurabh Sanghvi, Salil P. Vadhan: The Round Complexity of Two-Party Random Selection. SIAM J. Comput. 38(2): 523-550 (2008) |
2007 | ||
97 | Salil P. Vadhan: Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings Springer 2007 | |
96 | EE | Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee: Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO 2007: 264-283 |
95 | EE | Shien Jin Ong, Salil P. Vadhan: Zero Knowledge and Soundness Are Symmetric. EUROCRYPT 2007: 187-209 |
94 | EE | Salil P. Vadhan: The Complexity of Zero Knowledge. FSTTCS 2007: 52-70 |
93 | EE | Kai-Min Chung, Omer Reingold, Salil P. Vadhan: S-T Connectivity on Digraphs with a Known Stationary Distribution. IEEE Conference on Computational Complexity 2007: 236-249 |
92 | EE | Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. IEEE Conference on Computational Complexity 2007: 96-108 |
91 | EE | Oded Goldreich, Salil P. Vadhan: Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword. Computational Complexity 16(4): 325-330 (2007) |
90 | EE | Luca Trevisan, Salil P. Vadhan: Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16(4): 331-364 (2007) |
89 | EE | Kai-Min Chung, Omer Reingold, Salil P. Vadhan: S-T Connectivity on Digraphs with a Known Stationary Distribution. Electronic Colloquium on Computational Complexity (ECCC) 14(030): (2007) |
88 | EE | Dana Ron, Amir Rosenfeld, Salil P. Vadhan: The hardness of the Expected Decision Depth problem. Inf. Process. Lett. 101(3): 112-118 (2007) |
87 | EE | Boaz Barak, Shien Jin Ong, Salil P. Vadhan: Derandomization in Cryptography. SIAM J. Comput. 37(2): 380-400 (2007) |
86 | EE | Salil P. Vadhan: The unified theory of pseudorandomness: guest column. SIGACT News 38(3): 39-54 (2007) |
2006 | ||
85 | EE | Grant Schoenebeck, Salil P. Vadhan: The computational complexity of nash equilibria in concisely represented games. ACM Conference on Electronic Commerce 2006: 270-279 |
84 | EE | Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. CRYPTO 2006: 409-426 |
83 | EE | Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan: Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. FOCS 2006: 3-14 |
82 | EE | Minh-Huyen Nguyen, Salil P. Vadhan: Zero knowledge with efficient provers. STOC 2006: 287-295 |
81 | EE | Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC 2006: 457-466 |
80 | EE | Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman: Deterministic extractors for small-space sources. STOC 2006: 691-700 |
79 | EE | Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan: Concurrent Zero Knowledge Without Complexity Assumptions. TCC 2006: 1-20 |
78 | EE | Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. Electronic Colloquium on Computational Complexity (ECCC) 13(026): (2006) |
77 | EE | Salil P. Vadhan: An Unconditional Study of Computational Zero Knowledge. Electronic Colloquium on Computational Complexity (ECCC) 13(056): (2006) |
76 | EE | Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan: Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. Electronic Colloquium on Computational Complexity (ECCC) 13(075): (2006) |
75 | EE | Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Extractors and condensers from univariate polynomials. Electronic Colloquium on Computational Complexity (ECCC) 13(134): (2006) |
74 | EE | Shien Jin Ong, Salil P. Vadhan: Zero Knowledge and Soundness are Symmetric. Electronic Colloquium on Computational Complexity (ECCC) 13(139): (2006) |
73 | EE | Boaz Barak, Yehuda Lindell, Salil P. Vadhan: Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72(2): 321-391 (2006) |
72 | EE | Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using Nondeterminism to Amplify Hardness. SIAM J. Comput. 35(4): 903-931 (2006) |
71 | EE | Salil P. Vadhan: An Unconditional Study of Computational Zero Knowledge. SIAM J. Comput. 36(4): 1160-1214 (2006) |
70 | EE | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889-974 (2006) |
2005 | ||
69 | EE | Venkatesan Guruswami, Salil P. Vadhan: A Lower Bound on List Size for List Decoding. APPROX-RANDOM 2005: 318-329 |
68 | EE | Eyal Rozenman, Salil P. Vadhan: Derandomized Squaring of Graphs. APPROX-RANDOM 2005: 436-447 |
67 | EE | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Short PCPs Verifiable in Polylogarithmic Time. IEEE Conference on Computational Complexity 2005: 120-134 |
66 | EE | Saurabh Sanghvi, Salil P. Vadhan: The round complexity of two-party random selection. STOC 2005: 338-347 |
65 | EE | Salil P. Vadhan: Computational Complexity. Encyclopedia of Cryptography and Security 2005 |
64 | EE | Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Computational Complexity 14(3): 186-227 (2005) |
63 | EE | Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources Electronic Colloquium on Computational Complexity (ECCC)(012): (2005) |
62 | EE | Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem Electronic Colloquium on Computational Complexity (ECCC)(022): (2005) |
61 | EE | Grant Schoenebeck, Salil P. Vadhan: The Computational Complexity of Nash Equilibria in Concisely Represented Games Electronic Colloquium on Computational Complexity (ECCC)(052): (2005) |
60 | EE | Eyal Rozenman, Salil P. Vadhan: Derandomized Squaring of Graphs Electronic Colloquium on Computational Complexity (ECCC)(092): (2005) |
59 | EE | Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan: Concurrent Zero Knowledge without Complexity Assumptions Electronic Colloquium on Computational Complexity (ECCC)(093): (2005) |
58 | EE | Saurabh Sanghvi, Salil P. Vadhan: The Round Complexity of Two-Party Random Selection Electronic Colloquium on Computational Complexity (ECCC)(110): (2005) |
57 | EE | Boaz Barak, Shien Jin Ong, Salil P. Vadhan: Derandomization in Cryptography Electronic Colloquium on Computational Complexity (ECCC)(114): (2005) |
2004 | ||
56 | EE | Salil P. Vadhan: An Unconditional Study of Computational Zero Knowledge. FOCS 2004: 176-185 |
55 | EE | Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. IEEE Conference on Computational Complexity 2004: 1-14 |
54 | EE | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust pcps of proximity, shorter pcps and applications to coding. STOC 2004: 1-10 |
53 | EE | Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using nondeterminism to amplify hardness. STOC 2004: 192-201 |
52 | EE | Omer Reingold, Luca Trevisan, Salil P. Vadhan: Notions of Reducibility between Cryptographic Primitives. TCC 2004: 1-20 |
51 | EE | Minh-Huyen Nguyen, Salil P. Vadhan: Simpler Session-Key Generation from Short Random Passwords. TCC 2004: 428-445 |
50 | EE | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs and Applications to Coding Electronic Colloquium on Computational Complexity (ECCC)(021): (2004) |
49 | EE | Boaz Barak, Yehuda Lindell, Salil P. Vadhan: Lower Bounds for Non-Black-Box Zero Knowledge Electronic Colloquium on Computational Complexity (ECCC)(083): (2004) |
48 | EE | Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using Nondeterminism to Amplify Hardness Electronic Colloquium on Computational Complexity (ECCC)(087): (2004) |
47 | EE | Salil P. Vadhan: Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model. J. Cryptology 17(1): 43-77 (2004) |
2003 | ||
46 | EE | Daniele Micciancio, Salil P. Vadhan: Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More. CRYPTO 2003: 282-298 |
45 | EE | Boaz Barak, Shien Jin Ong, Salil P. Vadhan: Derandomization in Cryptography. CRYPTO 2003: 299-315 |
44 | EE | Salil P. Vadhan: On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model. CRYPTO 2003: 61-77 |
43 | EE | Boaz Barak, Yehuda Lindell, Salil P. Vadhan: Lower Bounds for Non-Black-Box Zero Knowledge. FOCS 2003: 384-393 |
42 | EE | Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Extractors: optimal up to constant factors. STOC 2003: 602-611 |
41 | EE | Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC 2003: 612-621 |
40 | EE | Amit Sahai, Salil P. Vadhan: A complete problem for statistical zero knowledge. J. ACM 50(2): 196-249 (2003) |
2002 | ||
39 | José D. P. Rolim, Salil P. Vadhan: Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings Springer 2002 | |
38 | EE | Salil P. Vadhan: Randomness Extractors and their Many Guises. FOCS 2002: 9- |
37 | EE | Luca Trevisan, Salil P. Vadhan: Pseudorandomness and Average-Case Complexity via Uniform Reductions. IEEE Conference on Computational Complexity 2002: 129-138 |
36 | EE | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness Conductors and Constant-Degree Lossless Expanders. IEEE Conference on Computational Complexity 2002: 15 |
35 | EE | Nenad Dedic, Leonid Reyzin, Salil P. Vadhan: An Improved Pseudorandom Generator Based on Hardness of Factoring. SCN 2002: 88-101 |
34 | EE | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness conductors and constant-degree lossless expanders. STOC 2002: 659-668 |
33 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1-53 (2002) |
32 | EE | Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan: The Power of a Pebble: Exploring and Mapping Directed Graphs. Inf. Comput. 176(1): 1-21 (2002) |
31 | EE | Ran Raz, Omer Reingold, Salil P. Vadhan: Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. J. Comput. Syst. Sci. 65(1): 97-128 (2002) |
2001 | ||
30 | EE | Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001: 1-18 |
29 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover. ICALP 2001: 334-345 |
28 | EE | Salil P. Vadhan: Order in Pseudorandomness. RANDOM-APPROX 2001: 10-11 |
27 | EE | Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs Electronic Colloquium on Computational Complexity (ECCC) 8(057): (2001) |
26 | EE | Omer Reingold, Salil P. Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors Electronic Colloquium on Computational Complexity (ECCC) 8(18): (2001) |
25 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover Electronic Colloquium on Computational Complexity (ECCC) 8(46): (2001) |
24 | Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2): 236-266 (2001) | |
23 | EE | Salil P. Vadhan: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM J. Comput. 31(2): 398-427 (2001) |
2000 | ||
22 | Omer Reingold, Salil P. Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. FOCS 2000: 3-13 | |
21 | Luca Trevisan, Salil P. Vadhan: Extracting Randomness from Samplable Distributions. FOCS 2000: 32-42 | |
20 | EE | Salil P. Vadhan: On transformation of interactive proofs that preserve the prover's complexity. STOC 2000: 200-207 |
19 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: Simplified derandomization of BPP using a hitting set generator. Electronic Colloquium on Computational Complexity (ECCC) 7(4): (2000) |
18 | EE | Amit Sahai, Salil P. Vadhan: A Complete Problem for Statistical Zero Knowledge Electronic Colloquium on Computational Complexity (ECCC) 7(84): (2000) |
1999 | ||
17 | EE | Oded Goldreich, Amit Sahai, Salil P. Vadhan: Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK. CRYPTO 1999: 467-484 |
16 | EE | Silvio Micali, Michael O. Rabin, Salil P. Vadhan: Verifiable Random Functions. FOCS 1999: 120-130 |
15 | EE | Ran Raz, Omer Reingold, Salil P. Vadhan: Error Reduction for Extractors. FOCS 1999: 191-201 |
14 | EE | Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma (Abstract). IEEE Conference on Computational Complexity 1999: 4 |
13 | EE | Oded Goldreich, Salil P. Vadhan: Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. IEEE Conference on Computational Complexity 1999: 54- |
12 | EE | Ran Raz, Omer Reingold, Salil P. Vadhan: Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. STOC 1999: 149-158 |
11 | EE | Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC 1999: 537-546 |
10 | EE | Oded Goldreich, Amit Sahai, Salil P. Vadhan: Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK Electronic Colloquium on Computational Complexity (ECCC) 6(13): (1999) |
9 | EE | Ran Raz, Omer Reingold, Salil P. Vadhan: Extracting All the Randomness and Reducing the Error in Trevisan's Extractors Electronic Colloquium on Computational Complexity (ECCC)(46): (1999) |
1998 | ||
8 | EE | Mihir Bellare, Shai Halevi, Amit Sahai, Salil P. Vadhan: Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems. CRYPTO 1998: 283-298 |
7 | EE | Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan: The Power of a Pebble: Exploring and Mapping Directed Graphs. STOC 1998: 269-278 |
6 | EE | Oded Goldreich, Amit Sahai, Salil P. Vadhan: Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. STOC 1998: 399-408 |
5 | EE | Daniel Lewin, Salil P. Vadhan: Checking Polynomial Identities over any Field: Towards a Derandomization? STOC 1998: 438-447 |
4 | EE | Salil P. Vadhan: Extracting All the Randomness from a Weakly Random Source Electronic Colloquium on Computational Complexity (ECCC) 5(47): (1998) |
3 | EE | Oded Goldreich, Salil P. Vadhan: Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK Electronic Colloquium on Computational Complexity (ECCC) 5(63): (1998) |
2 | EE | Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom generators without the XOR Lemma Electronic Colloquium on Computational Complexity (ECCC) 5(74): (1998) |
1997 | ||
1 | EE | Amit Sahai, Salil P. Vadhan: A Complete Promise Problem for Statistical Zero-Knowledge. FOCS 1997: 448-457 |