Paul Valiant
Purdue University, IN·Computer Science
Real-world data is rarely clean or complete. Algorithms often have to recover information, or make decisions that cannot be undone, while seeing only part of the input.
- Fields
Computer Science
Mathematics & Statistics
- Topics
algorithms
theoretical computer science
error-correcting codes
- Grants
- 2 known grants, last ended Sep 2026
What they work on
- Design error-correcting codes that withstand random or adversarial insertion and deletion errors while supporting local decoding, which recovers part of a message by reading only a small piece of the stored data.
- Develop methods to recover data in a learning model where noise damages the attributes (features) of examples, and analyze the limits of current techniques in this setting.
- Build online algorithms, which must make irreversible decisions as data arrives, in classical settings and when enhanced with machine-learning advice, and analyze the guarantees each can achieve.
- Develop efficient, accurate and robust algorithms for estimating the mean of a high-dimensional probability distribution from samples, using as little data as possible.
- Create frameworks that use knowledge of the data-collection process to make accurate statistical inferences from non-uniform, biased samples.
More about the research
That data may also be noisy, misaligned, or drawn from a biased sample. These two projects develop algorithms that stay fast, accurate and reliable under such conditions. They also prove mathematical limits on what any algorithm can achieve. The work draws on coding theory, learning theory, statistics, graph theory and optimization.
Why it matters
Algorithms that cope with damaged, partial or biased data could make DNA-based data storage, communication networks and machine-learning-assisted systems more reliable. Better ways to estimate averages from small, noisy or biased samples could help fields that rely on imperfect data, such as econometrics, sociology and computer graphics, to reach more accurate conclusions.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Ryan O'Donnell
Carnegie Mellon University, PA·Computer Science
Find new elementary methods for constructing high-dimensional expanders, highly interconnected mathematical networks, that avoid the advanced algebra and number theory used in current constructions.
Dana Dachman-Soled
University of Maryland, MD·Computer Science
Construct deterministic randomness extractors, which turn imperfect random sources into high-quality random bits, for efficiently samplable weak sources, including low-entropy classical and quantum sources and sources subject to leakage.
Zhiying Wang
University of California-Irvine, CA·Engineering·Early-career
Establish the fundamental limit on information density for composite DNA storage, where each position is a set mixture of A, C, G and T, and design coding schemes that reach it given symbol choice and storage-channel errors.
The school
Purdue University: 43 labs on PI Pages, $932M a year on research, 833 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.