Research on Complexity Theory

• Exponential algorithmic speedup by a quantum walk
  We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve thisproblem with high probability in subexponential time.

• Nearly linear-size holographic proofs
  Holographic proofs are also known as Probabilistically Checkable Proofs. We show that they can be suprisingly small. The main technical contribution is an improved analysis of "low-degree testing".

• Faster Isomorphism Testing of Strongly Regular Graphs
  We prove that isomorphism of strongly regular graphs can be tested in time roughly 2^n^(1/3).

• PP is closed under Intersection
  The title says it all. This was my first paper.

• Alternation in interaction
  We define and prove everything you would want to know about a generalization of PCP(log n, 1) to the polynomial time hierarchy.

• The Power of adaptiveness and additional queries in random-self-reductions
• A Remark on Matrix Rigidity