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:

Cryptography

See also: Zero-Knowledge Proofs.

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:

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:

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