Salil P. Vadhan

According to our database1, Salil P. Vadhan authored at least 246 papers between 1997 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Unifying computational entropies via Kullback-Leibler divergence.
IACR Cryptology ePrint Archive, 2019

Deterministic Approximation of Random Walks in Small Space.
CoRR, 2019

Unifying computational entropies via Kullback-Leibler divergence.
CoRR, 2019

Unifying Computational Entropies via Kullback-Leibler Divergence.
Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

Deterministic Approximation of Random Walks in Small Space.
Proceedings of the Approximation, 2019

2018
The Complexity of Computing the Optimal Composition of Differential Privacy.
Theory of Computing, 2018

Fingerprinting Codes and the Price of Approximate Differential Privacy.
SIAM J. Comput., 2018

Deterministic Public-Key Encryption for Adaptively-Chosen Plaintext Distributions.
J. Cryptology, 2018

A Tight Lower Bound for Entropy Flattening.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Usable Differential Privacy: A Case Study with PSI.
CoRR, 2018

Finite Sample Differentially Private Confidence Intervals.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Differential Privacy on Finite Computers.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

A Tight Lower Bound for Entropy Flattening.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs.
Theory of Computing, 2017

The Many Entropies in One-Way Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Finite Sample Differentially Private Confidence Intervals.
CoRR, 2017

Differential Privacy on Finite Computers.
CoRR, 2017

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
CoRR, 2017

Computational Notions of Quantum Min-Entropy.
CoRR, 2017

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

On Learning vs. Refutation.
Proceedings of the 30th Conference on Learning Theory, 2017

The Complexity of Differential Privacy.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017

The Many Entropies in One-Way Functions.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016
Truthful Mechanisms for Agents That Value Privacy.
ACM Trans. Economics and Comput., 2016

Separating Computational and Statistical Differential Privacy in the Client-Server Model.
IACR Cryptology ePrint Archive, 2016

Privacy Odometers and Filters: Pay-as-you-Go Composition.
CoRR, 2016

Locating a Small Cluster Privately.
CoRR, 2016

Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing.
CoRR, 2016

PSI (Ψ): a Private data Sharing Interface.
CoRR, 2016

Towards a Privacy Research Roadmap for the Computing Community.
CoRR, 2016

The Complexity of Computing the Optimal Composition of Differential Privacy.
Proceedings of the Theory of Cryptography - 13th International Conference, 2016

Separating Computational and Statistical Differential Privacy in the Client-Server Model.
Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Locating a Small Cluster Privately.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Privacy Odometers and Filters: Pay-as-you-Go Composition.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing.
Proceedings of the 33nd International Conference on Machine Learning, 2016

2015
The Complexity of Computing the Optimal Composition of Differential Privacy.
IACR Cryptology ePrint Archive, 2015

The Complexity of Computing the Optimal Composition of Differential Privacy.
CoRR, 2015

Pseudorandomness for Read-Once, Constant-Depth Circuits.
CoRR, 2015

Differentially Private Release and Learning of Threshold Functions.
CoRR, 2015

Robust Traceability from Trace Amounts.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Differentially Private Release and Learning of Threshold Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs.
CoRR, 2014

Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals.
CoRR, 2014

Privacy Games.
CoRR, 2014

Privacy Games.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Fingerprinting codes and the price of approximate differential privacy.
Proceedings of the Symposium on Theory of Computing, 2014

Redrawing the boundaries on purchasing data from privacy-sensitive individuals.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Locally testable codes and cayley graphs.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs.
Proceedings of the Approximation, 2014

2013
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream.
Theory of Computing, 2013

Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions.
SIAM J. Comput., 2013

On extractors and exposure-resilient functions for sublogarithmic entropy.
Random Struct. Algorithms, 2013

A Uniform Min-Max Theorem with Applications in Cryptography.
IACR Cryptology ePrint Archive, 2013

Deterministic Public-Key Encryption for Adaptively Chosen Plaintext Distributions.
IACR Cryptology ePrint Archive, 2013

A Uniform Min-Max Theorem with Applications in Cryptography.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Locally Testable Codes and Cayley Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Pseudorandomness for Regular Branching Programs via Fourier Analysis.
CoRR, 2013

Locally Testable Codes and Cayley Graphs.
CoRR, 2013

Fingerprinting Codes and the Price of Approximate Differential Privacy.
CoRR, 2013

Interactive proofs of proximity: delegating computation in sublinear time.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Truthful mechanisms for agents that value privacy.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Publicly verifiable proofs of sequential work.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Deterministic Public-Key Encryption for Adaptively Chosen Plaintext Distributions.
Proceedings of the Advances in Cryptology, 2013

A Uniform Min-Max Theorem with Applications in Cryptography.
Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
The Computational Complexity of Nash Equilibria in Concisely Represented Games.
TOCT, 2012

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).
SIAM J. Comput., 2012

On the (im)possibility of obfuscating programs.
J. ACM, 2012

Differential Privacy with Imperfect Randomness.
IACR Cryptology ePrint Archive, 2012

Pseudorandomness.
Foundations and Trends in Theoretical Computer Science, 2012

Better pseudorandom generators from milder pseudorandom restrictions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions
CoRR, 2012

Faster Algorithms for Privately Releasing Marginals
CoRR, 2012

Special issue from RANDOM'09: Editors' Foreword.
Computational Complexity, 2012

Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources.
Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Characterizing pseudoentropy and simplifying pseudorandom generator constructions.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Characterizing pseudoentropy.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012

Faster Algorithms for Privately Releasing Marginals.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

The Privacy of the Analyst and the Power of the State.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Differential Privacy with Imperfect Randomness.
Proceedings of the Advances in Cryptology - CRYPTO 2012, 2012

2011
S-T connectivity on digraphs with a known stationary distribution.
ACM Trans. Algorithms, 2011

Deterministic extractors for small-space sources.
J. Comput. Syst. Sci., 2011

Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model.
IACR Cryptology ePrint Archive, 2011

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions.
Electronic Colloquium on Computational Complexity (ECCC), 2011

The Limits of Two-Party Differential Privacy.
Electronic Colloquium on Computational Complexity (ECCC), 2011

On the complexity of computational problems regarding distributions (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 2011

Truthful Mechanisms for Agents that Value Privacy
CoRR, 2011

PCPs and the Hardness of Generating Private Synthetic Data.
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

On Approximating the Entropy of Polynomial Mappings.
Proceedings of the Innovations in Computer Science, 2011

Time-Lock Puzzles in the Random Oracle Model.
Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Complexity of Computational Problems Regarding Distributions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
A Lower Bound on List Size for List Decoding.
IEEE Trans. Information Theory, 2010

Universal One-Way Hash Functions via Inaccessible Entropy.
IACR Cryptology ePrint Archive, 2010

Improved Delegation of Computation using Fully Homomorphic Encryption.
IACR Cryptology ePrint Archive, 2010

PCPs and the Hardness of Generating Synthetic Data.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On Approximating the Entropy of Polynomial Mappings.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy
CoRR, 2010

Are PCPs Inherent in Efficient Arguments?
Computational Complexity, 2010

Composition of Zero-Knowledge Proofs with Efficient Provers.
Proceedings of the Theory of Cryptography, 7th Theory of Cryptography Conference, 2010

Efficiency improvements in constructing pseudorandom generators from one-way functions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

The Limits of Two-Party Differential Privacy.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Boosting and Differential Privacy.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Universal One-Way Hash Functions via Inaccessible Entropy.
Proceedings of the Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30, 2010

Improved Delegation of Computation Using Fully Homomorphic Encryption.
Proceedings of the Advances in Cryptology, 2010

2009
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
SIAM J. Comput., 2009

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.
J. ACM, 2009

Proofs of Retrievability via Hardness Amplification.
IACR Cryptology ePrint Archive, 2009

Composition of Zero-Knowledge Proofs with Efficient Provers.
IACR Cryptology ePrint Archive, 2009

Are PCPs Inherent in Efficient Arguments?
Electronic Colloquium on Computational Complexity (ECCC), 2009

Inaccessible Entropy.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Fairness with an Honest Minority and a Rational Majority.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Proofs of Retrievability via Hardness Amplification.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Inaccessible entropy.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

On the complexity of differentially private data release: efficient algorithms and hardness results.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Computational Differential Privacy.
Proceedings of the Advances in Cryptology, 2009

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Are PCPs Inherent in Efficient Arguments?
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

2008
The Round Complexity of Two-Party Random Selection.
SIAM J. Comput., 2008

Simpler Session-Key Generation from Short Random Passwords.
J. Cryptology, 2008

Fairness with an Honest Minority and a Rational Majority.
IACR Cryptology ePrint Archive, 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Limitations of Hardness vs. Randomness under Uniform Reductions.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Tight Bounds for Hashing Block Sources
CoRR, 2008

An Equivalence Between Zero Knowledge and Commitments.
Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model.
Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Why simple hash functions work: exploiting the entropy in a data stream.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Dense Subsets of Pseudorandom Sets.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Limitations of Hardness vs. Randomness under Uniform Reductions.
Proceedings of the Approximation, 2008

Tight Bounds for Hashing Block Sources.
Proceedings of the Approximation, 2008

The Complexity of Distinguishing Markov Random Fields.
Proceedings of the Approximation, 2008

2007
The unified theory of pseudorandomness: guest column.
SIGACT News, 2007

Derandomization in Cryptography.
SIAM J. Comput., 2007

The hardness of the Expected Decision Depth problem.
Inf. Process. Lett., 2007

Interactive and Noninteractive Zero Knowledge Coincide in the Help Model.
IACR Cryptology ePrint Archive, 2007

Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model.
IACR Cryptology ePrint Archive, 2007

S-T Connectivity on Digraphs with a Known Stationary Distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Computational Complexity, 2007

Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Computational Complexity, 2007

The Complexity of Zero Knowledge.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Zero Knowledge and Soundness Are Symmetric.
Proceedings of the Advances in Cryptology, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007

Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

S-T Connectivity on Digraphs with a Known Stationary Distribution.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
An Unconditional Study of Computational Zero Knowledge.
SIAM J. Comput., 2006

Using Nondeterminism to Amplify Hardness.
SIAM J. Comput., 2006

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput., 2006

Lower bounds for non-black-box zero knowledge.
J. Comput. Syst. Sci., 2006

Zero Knowledge and Soundness are Symmetric.
IACR Cryptology ePrint Archive, 2006

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
IACR Cryptology ePrint Archive, 2006

An Unconditional Study of Computational Zero Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Zero Knowledge and Soundness are Symmetric.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Random Selection with an Adversarial Majority.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Concurrent Zero Knowledge Without Complexity Assumptions.
Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference, 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Zero knowledge with efficient provers.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Deterministic extractors for small-space sources.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The computational complexity of nash equilibria in concisely represented games.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Random Selection with an Adversarial Majority.
Proceedings of the Advances in Cryptology, 2006

2005
Computational Complexity.
Proceedings of the Encyclopedia of Cryptography and Security, 2005

Concurrent Zero Knowledge without Complexity Assumptions.
IACR Cryptology ePrint Archive, 2005

Derandomization in Cryptography.
IACR Cryptology ePrint Archive, 2005

Derandomization in Cryptography
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Round Complexity of Two-Party Random Selection
Electronic Colloquium on Computational Complexity (ECCC), 2005

Concurrent Zero Knowledge without Complexity Assumptions
Electronic Colloquium on Computational Complexity (ECCC), 2005

Derandomized Squaring of Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Computational Complexity of Nash Equilibria in Concisely Represented Games
Electronic Colloquium on Computational Complexity (ECCC), 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

Compression of Samplable Sources
Electronic Colloquium on Computational Complexity (ECCC), 2005

Compression of Samplable Sources.
Computational Complexity, 2005

The round complexity of two-party random selection.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Derandomized Squaring of Graphs.
Proceedings of the Approximation, 2005

A Lower Bound on List Size for List Decoding.
Proceedings of the Approximation, 2005

2004
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
J. Cryptology, 2004

Simpler Session-Key Generation from Short Random Passwords.
IACR Cryptology ePrint Archive, 2004

Lower Bounds for Non-Black-Box Zero Knowledge.
IACR Cryptology ePrint Archive, 2004

Using Nondeterminism to Amplify Hardness
Electronic Colloquium on Computational Complexity (ECCC), 2004

Lower Bounds for Non-Black-Box Zero Knowledge
Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electronic Colloquium on Computational Complexity (ECCC), 2004

Notions of Reducibility between Cryptographic Primitives.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Simpler Session-Key Generation from Short Random Passwords.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Using nondeterminism to amplify hardness.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Robust pcps of proximity, shorter pcps and applications to coding.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

An Unconditional Study of Computational Zero Knowledge.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Compression of Samplable Sources.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Probabilistic proof systems - Part I.
Proceedings of the Computational Complexity Theory., 2004

2003
A complete problem for statistical zero knowledge.
J. ACM, 2003

Extractors: optimal up to constant factors.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Lower Bounds for Non-Black-Box Zero Knowledge.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model.
Proceedings of the Advances in Cryptology, 2003

Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.
Proceedings of the Advances in Cryptology, 2003

Derandomization in Cryptography.
Proceedings of the Advances in Cryptology, 2003

2002
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci., 2002

The Power of a Pebble: Exploring and Mapping Directed Graphs.
Inf. Comput., 2002

On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model.
IACR Cryptology ePrint Archive, 2002

An Improved Pseudorandom Generator Based on Hardness of Factoring.
IACR Cryptology ePrint Archive, 2002

On interactive proofs with a laconic prover.
Computational Complexity, 2002

An Improved Pseudorandom Generator Based on Hardness of Factoring.
Proceedings of the Security in Communication Networks, Third International Conference, 2002

Randomness Extractors and their Many Guises.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Pseudorandomness and Average-Case Complexity via Uniform Reductions.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Randomness Conductors and Constant-Degree Lossless Expanders.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
The Complexity of Counting in Sparse, Regular, and Planar Graphs.
SIAM J. Comput., 2001

Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001

On the (Im)possibility of Obfuscating Programs.
IACR Cryptology ePrint Archive, 2001

On the (Im)possibility of Obfuscating Programs
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Interactive Proofs with a Laconic Prover
Electronic Colloquium on Computational Complexity (ECCC), 2001

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electronic Colloquium on Computational Complexity (ECCC), 2001

Order in Pseudorandomness.
Proceedings of the Approximation, 2001

On Interactive Proofs with a Laconic Prover.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

On the (Im)possibility of Obfuscating Programs.
Proceedings of the Advances in Cryptology, 2001

2000
A Complete Problem for Statistical Zero Knowledge.
IACR Cryptology ePrint Archive, 2000

A Complete Problem for Statistical Zero Knowledge
Electronic Colloquium on Computational Complexity (ECCC), 2000

Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC), 2000

On transformation of interactive proofs that preserve the prover's complexity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness from Samplable Distributions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Extracting All the Randomness and Reducing the Error in Trevisan's Extractors
Electronic Colloquium on Computational Complexity (ECCC), 1999

Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Electronic Colloquium on Computational Complexity (ECCC), 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Error Reduction for Extractors.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Verifiable Random Functions.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK.
Proceedings of the Advances in Cryptology, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK.
IACR Cryptology ePrint Archive, 1998

Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems.
IACR Cryptology ePrint Archive, 1998

Pseudorandom generators without the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1998

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
Electronic Colloquium on Computational Complexity (ECCC), 1998

Extracting All the Randomness from a Weakly Random Source
Electronic Colloquium on Computational Complexity (ECCC), 1998

Checking Polynomial Identities over any Field: Towards a Derandomization?
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Power of a Pebble: Exploring and Mapping Directed Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems.
Proceedings of the Advances in Cryptology, 1998

1997
A Complete Promise Problem for Statistical Zero-Knowledge.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Manipulating statistical difference.
Proceedings of the Randomization Methods in Algorithm Design, 1997


  Loading...