Purdue University - Department of Computer Science - Paul Valiant Skip to main content

Paul Valiant


Joined department: Fall 2021


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.

Last Updated: Dec 4, 2020 1:55 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone: (765) 494-6010 • Fax: (765) 494-0739

Copyright © 2020 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.