Ronitt Rubinfeld

Rubinfeld has made foundational contributions to the theory of algorithms, in particular towards isolating the criteria by which performance of algorithms that work without reading all the input data, but by merely sampling portions of it, ought to be measured. The resulting theory, studied under the label of sublinear time algorithms, is a result of a long stream of collaborative works, with Rubinfeld being the lead person at the center of this research. These works have collectively influenced the practice of algorithm design while also ushering in a mathematical revolution via the fields of property testing and linearity testing. Some works that deserve special mention include her work on linearity testing with Blum and Luby in 1993  that introduced a simple problem-how to test if a multivariate function is close to being linear-along with a simple solution with highly subtle analysis. This problem and solution have revolutionized theoretical computer science by its central role in the so-called PCP theorem,  and have been the starting point for connections between theoretical computer science and Fourier analysis. Her later works  extended the study to testing general properties including statistical properties, connecting the field to central questions in statistics.