Descriptions of Salil Vadhan's Research


One of the main goals of the Theory of Computation, and complexity theory in particular, is to quantify the resources needed to accomplish useful computational tasks.  The most traditional interpretation of this is to determine the time and space needed to compute various functions.  Over time, the scope of complexity theory has broadened to consider a wider range of computational tasks, ranging from secure multiparty computations to explicit constructions of combinatorial objects, and additional resources, such as interaction and randomness.   Most of my research focuses on these kinds of computational tasks and resources, particularly as they relate to cryptography and randomized computations.

Below there are descriptions of some more specific topics which I have investigated.

Interactive Proofs & Zero-Knowledge Proofs

The notion of a proof  is central to mathematics and computer science.  Indeed, it has been long understood that properties of traditional mathematical  proofs are intimately connected to the fundamental questions of complexity theory (e.g., P vs. NP and NP vs. co-NP).   In the mid 80's, Goldwasser, Micali, and Rackoff [GMR] and Babai [Bab], proposed generalizations of the traditional notion of proof, known as interactive proofs, which have been at the center of some very exciting developments in complexity theory and cryptography.  The two new ingredients in interactive proofs are randomization  --- verification of proofs is probabilistic and may err with some small probability --- and interaction --- the traditional "written" proof is replaced with a dynamic, all-powerful prover which tries to convince a polynomial-time verifier that some assertion is true.

Zero-knowledge proofs are interactive proofs with the amazing property that the verifier learns nothing from its interaction with the prover, other than the fact that the assertion being proven is true.  Zero-knowledge proofs have vast applicability in constructing secure cryptographic protocols.  Much of my work has taken a complexity-theoretic approach to developing our understanding of zero-knowledge proofs: characterizing the classes of problems having various kinds of zero-knowledge proofs (e.g. via complete problems), proving general theorems about zero-knowledge proofs, and trying to minimize or eliminate the complexity assumptions used in the study of zero knowledge.  
 

For more background:

My papers on this topic:

Pseudorandomness

The surprising power of randomization is one of the most fascinating phenomena in computer science. By allowing algorithms to ``flip coins,'' we are able to efficiently solve many problems that we do not know how to efficiently solve otherwise.  Randomization is also a powerful tool for proving the existence of useful combinatorial objects, such as error-correcting codes and ``expander graphs'' (sparse graphs with very strong connectivity properties), as one can often prove that a ``random'' object has the desired properties.  However, we still do not know to what extent the randomness is really necessary  in these settings, and understanding this is an important goal.  One reason is that it is unclear whether there exist sufficiently good sources of randomness in nature to reliably run randomized algorithms.  Another is that, for the case of combinatorial constructions, the ``random objects'' often require an exponentially large description are hence infeasible to use.  Thus, we ask:   Can the need for randomness in these settings be eliminated, or at least reduced?  More concretely:  Can randomized algorithms be simulated using a  defective source of randomness, and how great a loss of efficiency must be incurred to do so?  Or can we even completely remove the use of randomness from a randomized algorithm with only a small loss in efficiency?  Can we deterministically construct objects such as expander graphs that perform as well as the random constructions?  These questions are addressed by the paradigm of pseudorandomness, which is concerned with efficiently generating objects that ``look random'' despite being constructed using less or defective randomness (or even deterministically).
 

For more background:

My papers on this topic:

Data Privacy 

The enormous amount of data being collected by researchers, governments, and companies on individuals contains information that, on one hand, can be used for great societal benefit, but on the other hand, poses a severe threat to privacy. Computer science research on data privacy seeks to provide algorithms that enable sharing useful information computed on such data sets while protecting privacy of the individuals whose data is used. A particularly appealing model for privacy guarantees is the recent notion of differential privacy, which requires releasing information in a randomized ("noisy") way so that the output distribution is insensitive to the presence or absence of any one individual. (See the surveys on the Microsoft Research page below for more about differential privacy.) I have been particularly interested in the effect of computational complexity on differential privacy --- constraining the computational resources of either the privacy mechanism/curator (making privacy harder) or the adversary (making privacy easier). My interest in data privacy was sparked by and continues to be influenced by my involvement with the Harvard Center for Research on Computation and Society.

For more background:

My papers on this topic:

Other Computational Complexity

My interests extend to many other topics in computational complexity theory (and indeed the Theory of Computation at large).  Some particular topics I have focused on include the complexity of Counting Problems and the design of efficient probabilistically checkable proof systems (PCPs). 

For more background:

My papers on the complexity of counting:

My papers on PCPs:

Other Cryptography

Over the past 25 years, research has made it possible to develop cryptographic systems that are provably secure based on precise assumptions about the hardness of various computational problems, such as factoring.  Between the hard problems and the final applications lie the primitives, which accomplish basic cryptographic tasks (such as encryption and authentication) that are useful in a wide variety of cryptographic protocols.  My research interests in this area is centered around these primitives --- designing new primitives to solve natural cryptographic problems, obtaining more efficient constructions of existing primitives, determining the minimal assumptions needed for them, and exploring the relationships among them.

For more background:

My papers on this topic:

[ Back to Salil's Home Page ]
This page was last updated 11/4/10.