简介

I have broad interests, with a focus on computational complexity---the study of the inherent limits of efficient computation. Specific interests include: • achieving a better understanding of the limits of powerful algorithmic paradigms for solving NP-hard problems, such as kernelization (efficient preprocessing of the input) and intelligent random guessing to obtain solutions; • the study of non-standard proof systems, which incorporate features like interaction with provers, probabilistic verification, and the manipulation of quantum states; • prospects and limits to efficient joint computation, in cases where we have multiple computational tasks to perform simultaneously, and where we may hope cleverly combine computations to make them more efficient and reliable. Outside of complexity theory, I've worked on problems in prediction and polynomial approximation. I also have a personal interest in using algorithmic ideas to better understand the power of human memory.