Paul Valiant

About Me

me

My research interests are in algorithms and complexity, fluid dynamics, machine learning, and the brain.

My algorithmic research focuses on sublinear algorithms on big data and related statistics. One branch of this research aims at illuminating the "unseen" portion of a probability distribution - what does the data about customers that visited a website this month enable us to say about the set of customers that did not visit the website? While this entire line of research aims to glean as much value from limited or expensive data as possible, in some cases the algorithms have achieved an unusually high bar: "instance optimal" algorithms, general-purpose algorithms that are competitive on each instance even compared to an algorithm custom-designed for that particular instance. Complementing and reinforcing all this work is a focus on developing matching lower bounds; algorithmic lower bounds typically rely on rather different techniques than the algorithms themselves, yet provide an invaluable source of illumination for future algorithmic work in the area.

My fluid dynamics work is focused on discovering structures, regularities, and invariants, using a mixture of computer-aided proof techniques, multi-scale simulations and visualizations, and traditional mathematical analysis.

I am also investigating the complementary perspectives provided by machine learning and human cognition: the brain and its evolutionary development provide tantalizing hints of new possibilities in machine learning, while scientific efforts to understand the power and limitations of machine learning and deep learning provide powerful new guidance to understand how the brain accomplishes analogous tasks. I am particularly interested in understanding the cerebellum's algorithmic role in the brain.

Teaching:

In the fall, I teach Algorithms; in the spring I usually teach a graduate reading seminar, CSCI 2951M.