 | 2009 |
|---|
| 117 |       | Shachar Lovett,
Omer Reingold,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Bit Generators That Fool Modular Sums.
APPROX-RANDOM 2009: 615-630 |
| 116 | | Ilya Mironov,
Omkant Pandey,
Omer Reingold,
Salil P. Vadhan:
Computational Differential Privacy.
CRYPTO 2009: 126-142 |
| 115 | | Cynthia Dwork,
Moni Naor,
Omer Reingold,
Guy N. Rothblum,
Salil P. Vadhan:
On the complexity of differentially private data release: efficient algorithms and hardness results.
STOC 2009: 381-390 |
| 114 | | Iftach Haitner,
Omer Reingold,
Salil P. Vadhan,
Hoeteck Wee:
Inaccessible entropy.
STOC 2009: 611-620 |
| 113 | | Yevgeniy Dodis,
Salil P. Vadhan,
Daniel Wichs:
Proofs of Retrievability via Hardness Amplification.
TCC 2009: 109-127 |
| 112 | | Shien Jin Ong,
David C. Parkes,
Alon Rosen,
Salil P. Vadhan:
Fairness with an Honest Minority and a Rational Majority.
TCC 2009: 36-53 |
| 111 | | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes.
J. ACM 56(4): (2009) |
| 2008 |
|---|
| 110 | | Andrej Bogdanov,
Elchanan Mossel,
Salil P. Vadhan:
The Complexity of Distinguishing Markov Random Fields.
APPROX-RANDOM 2008: 331-342 |
| 109 | | Kai-Min Chung,
Salil P. Vadhan:
Tight Bounds for Hashing Block Sources.
APPROX-RANDOM 2008: 357-370 |
| 108 | | Dan Gutfreund,
Salil P. Vadhan:
Limitations of Hardness vs. Randomness under Uniform Reductions.
APPROX-RANDOM 2008: 469-482 |
| 107 | | Omer Reingold,
Luca Trevisan,
Madhur Tulsiani,
Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets.
FOCS 2008: 76-85 |
| 106 | | Michael Mitzenmacher,
Salil P. Vadhan:
Why simple hash functions work: exploiting the entropy in a data stream.
SODA 2008: 746-755 |
| 105 | | Shien Jin Ong,
Salil P. Vadhan:
An Equivalence Between Zero Knowledge and Commitments.
TCC 2008: 482-500 |
| 104 | | 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 | | Kai-Min Chung,
Salil P. Vadhan:
Tight Bounds for Hashing Block Sources
CoRR abs/0806.1948: (2008) |
| 102 | | Dan Gutfreund,
Salil P. Vadhan:
Limitations of Hardness vs. Randomness under Uniform Reductions.
Electronic Colloquium on Computational Complexity (ECCC) 15(007): (2008) |
| 101 | | Omer Reingold,
Luca Trevisan,
Madhur Tulsiani,
Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC) 15(045): (2008) |
| 100 | | 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 | | Minh-Huyen Nguyen,
Salil P. Vadhan:
Simpler Session-Key Generation from Short Random Passwords.
J. Cryptology 21(1): 52-96 (2008) |
| 98 | | 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 | | 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 | | Shien Jin Ong,
Salil P. Vadhan:
Zero Knowledge and Soundness Are Symmetric.
EUROCRYPT 2007: 187-209 |
| 94 | | Salil P. Vadhan:
The Complexity of Zero Knowledge.
FSTTCS 2007: 52-70 |
| 93 | | 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 | | 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 | | Oded Goldreich,
Salil P. Vadhan:
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Computational Complexity 16(4): 325-330 (2007) |
| 90 | | Luca Trevisan,
Salil P. Vadhan:
Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Computational Complexity 16(4): 331-364 (2007) |
| 89 | | 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 | | Dana Ron,
Amir Rosenfeld,
Salil P. Vadhan:
The hardness of the Expected Decision Depth problem.
Inf. Process. Lett. 101(3): 112-118 (2007) |
| 87 | | Boaz Barak,
Shien Jin Ong,
Salil P. Vadhan:
Derandomization in Cryptography.
SIAM J. Comput. 37(2): 380-400 (2007) |
| 86 | | Salil P. Vadhan:
The unified theory of pseudorandomness: guest column.
SIGACT News 38(3): 39-54 (2007) |
| 2006 |
|---|
| 85 | | Grant Schoenebeck,
Salil P. Vadhan:
The computational complexity of nash equilibria in concisely represented games.
ACM Conference on Electronic Commerce 2006: 270-279 |
| 84 | | Ronen Gradwohl,
Salil P. Vadhan,
David Zuckerman:
Random Selection with an Adversarial Majority.
CRYPTO 2006: 409-426 |
| 83 | | 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 | | Minh-Huyen Nguyen,
Salil P. Vadhan:
Zero knowledge with efficient provers.
STOC 2006: 287-295 |
| 81 | | Omer Reingold,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom walks on regular digraphs and the RL vs. L problem.
STOC 2006: 457-466 |
| 80 | | Jesse Kamp,
Anup Rao,
Salil P. Vadhan,
David Zuckerman:
Deterministic extractors for small-space sources.
STOC 2006: 691-700 |
| 79 | | Daniele Micciancio,
Shien Jin Ong,
Amit Sahai,
Salil P. Vadhan:
Concurrent Zero Knowledge Without Complexity Assumptions.
TCC 2006: 1-20 |
| 78 | | Ronen Gradwohl,
Salil P. Vadhan,
David Zuckerman:
Random Selection with an Adversarial Majority.
Electronic Colloquium on Computational Complexity (ECCC) 13(026): (2006) |
| 77 | | Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge.
Electronic Colloquium on Computational Complexity (ECCC) 13(056): (2006) |
| 76 | | 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 | | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC) 13(134): (2006) |
| 74 | | Shien Jin Ong,
Salil P. Vadhan:
Zero Knowledge and Soundness are Symmetric.
Electronic Colloquium on Computational Complexity (ECCC) 13(139): (2006) |
| 73 | | 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 | | Alexander Healy,
Salil P. Vadhan,
Emanuele Viola:
Using Nondeterminism to Amplify Hardness.
SIAM J. Comput. 35(4): 903-931 (2006) |
| 71 | | Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge.
SIAM J. Comput. 36(4): 1160-1214 (2006) |
| 70 | | 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 | | Venkatesan Guruswami,
Salil P. Vadhan:
A Lower Bound on List Size for List Decoding.
APPROX-RANDOM 2005: 318-329 |
| 68 | | Eyal Rozenman,
Salil P. Vadhan:
Derandomized Squaring of Graphs.
APPROX-RANDOM 2005: 436-447 |
| 67 | | 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 | | Saurabh Sanghvi,
Salil P. Vadhan:
The round complexity of two-party random selection.
STOC 2005: 338-347 |
| 65 | | Salil P. Vadhan:
Computational Complexity.
Encyclopedia of Cryptography and Security 2005 |
| 64 | | Luca Trevisan,
Salil P. Vadhan,
David Zuckerman:
Compression of Samplable Sources.
Computational Complexity 14(3): 186-227 (2005) |
| 63 | | Luca Trevisan,
Salil P. Vadhan,
David Zuckerman:
Compression of Samplable Sources
Electronic Colloquium on Computational Complexity (ECCC)(012): (2005) |
| 62 | | 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 | | Grant Schoenebeck,
Salil P. Vadhan:
The Computational Complexity of Nash Equilibria in Concisely Represented Games
Electronic Colloquium on Computational Complexity (ECCC)(052): (2005) |
| 60 | | Eyal Rozenman,
Salil P. Vadhan:
Derandomized Squaring of Graphs
Electronic Colloquium on Computational Complexity (ECCC)(092): (2005) |
| 59 | | 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 | | Saurabh Sanghvi,
Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection
Electronic Colloquium on Computational Complexity (ECCC)(110): (2005) |
| 57 | | Boaz Barak,
Shien Jin Ong,
Salil P. Vadhan:
Derandomization in Cryptography
Electronic Colloquium on Computational Complexity (ECCC)(114): (2005) |
| 2004 |
|---|
| 56 | | Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge.
FOCS 2004: 176-185 |
| 55 | | Luca Trevisan,
Salil P. Vadhan,
David Zuckerman:
Compression of Samplable Sources.
IEEE Conference on Computational Complexity 2004: 1-14 |
| 54 | | 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 | | Alexander Healy,
Salil P. Vadhan,
Emanuele Viola:
Using nondeterminism to amplify hardness.
STOC 2004: 192-201 |
| 52 | | Omer Reingold,
Luca Trevisan,
Salil P. Vadhan:
Notions of Reducibility between Cryptographic Primitives.
TCC 2004: 1-20 |
| 51 | | Minh-Huyen Nguyen,
Salil P. Vadhan:
Simpler Session-Key Generation from Short Random Passwords.
TCC 2004: 428-445 |
| 50 | | 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 | | Boaz Barak,
Yehuda Lindell,
Salil P. Vadhan:
Lower Bounds for Non-Black-Box Zero Knowledge
Electronic Colloquium on Computational Complexity (ECCC)(083): (2004) |
| 48 | | Alexander Healy,
Salil P. Vadhan,
Emanuele Viola:
Using Nondeterminism to Amplify Hardness
Electronic Colloquium on Computational Complexity (ECCC)(087): (2004) |
| 47 | | Salil P. Vadhan:
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
J. Cryptology 17(1): 43-77 (2004) |
| 2003 |
|---|
| 46 | | Daniele Micciancio,
Salil P. Vadhan:
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.
CRYPTO 2003: 282-298 |
| 45 | | Boaz Barak,
Shien Jin Ong,
Salil P. Vadhan:
Derandomization in Cryptography.
CRYPTO 2003: 299-315 |
| 44 | | Salil P. Vadhan:
On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model.
CRYPTO 2003: 61-77 |
| 43 | | Boaz Barak,
Yehuda Lindell,
Salil P. Vadhan:
Lower Bounds for Non-Black-Box Zero Knowledge.
FOCS 2003: 384-393 |
| 42 | | Chi-Jen Lu,
Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Extractors: optimal up to constant factors.
STOC 2003: 602-611 |
| 41 | | 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 | | 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 | | Salil P. Vadhan:
Randomness Extractors and their Many Guises.
FOCS 2002: 9- |
| 37 | | Luca Trevisan,
Salil P. Vadhan:
Pseudorandomness and Average-Case Complexity via Uniform Reductions.
IEEE Conference on Computational Complexity 2002: 129-138 |
| 36 | | 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 | | Nenad Dedic,
Leonid Reyzin,
Salil P. Vadhan:
An Improved Pseudorandom Generator Based on Hardness of Factoring.
SCN 2002: 88-101 |
| 34 | | Michael R. Capalbo,
Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Randomness conductors and constant-degree lossless expanders.
STOC 2002: 659-668 |
| 33 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
On interactive proofs with a laconic prover.
Computational Complexity 11(1-2): 1-53 (2002) |
| 32 | | 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 | | 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 | | 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 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
On Interactive Proofs with a Laconic Prover.
ICALP 2001: 334-345 |
| 28 | | Salil P. Vadhan:
Order in Pseudorandomness.
RANDOM-APPROX 2001: 10-11 |
| 27 | | 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 | | 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 | | 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 | | 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 | | Salil P. Vadhan:
On transformation of interactive proofs that preserve the prover's complexity.
STOC 2000: 200-207 |
| 19 | | 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 | | Amit Sahai,
Salil P. Vadhan:
A Complete Problem for Statistical Zero Knowledge
Electronic Colloquium on Computational Complexity (ECCC) 7(84): (2000) |
| 1999 |
|---|
| 17 | | 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 | | Silvio Micali,
Michael O. Rabin,
Salil P. Vadhan:
Verifiable Random Functions.
FOCS 1999: 120-130 |
| 15 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Error Reduction for Extractors.
FOCS 1999: 191-201 |
| 14 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma (Abstract).
IEEE Conference on Computational Complexity 1999: 4 |
| 13 | | 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 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
STOC 1999: 149-158 |
| 11 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
STOC 1999: 537-546 |
| 10 | | 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 | | 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 | | 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 | | 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 | | Oded Goldreich,
Amit Sahai,
Salil P. Vadhan:
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
STOC 1998: 399-408 |
| 5 | | Daniel Lewin,
Salil P. Vadhan:
Checking Polynomial Identities over any Field: Towards a Derandomization?
STOC 1998: 438-447 |
| 4 | | Salil P. Vadhan:
Extracting All the Randomness from a Weakly Random Source
Electronic Colloquium on Computational Complexity (ECCC) 5(47): (1998) |
| 3 | | 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 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom generators without the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC) 5(74): (1998) |
| 1997 |
|---|
| 1 | | Amit Sahai,
Salil P. Vadhan:
A Complete Promise Problem for Statistical Zero-Knowledge.
FOCS 1997: 448-457 |
