I am broadly interested in algorithms and computational complexity, primarily focusing on the following three research goals.
Understanding the power of low-degree polynomials to approximate Boolean functions. Answering these questions has a variety of applications, especially to quantum computing, learning theory, and computational complexity theory.
Designing protocols for proving the correctness of computations (possibly in zero-knowlege), in which the prover and verifier are highly efficient both in the