Tata Institute of Fundamental Research
Testing for (algebraic) patterns in data
TIFR Colloquium
Speaker:
Madhu Sudan (Harvard John A. Poulson School of Engineering and Applied Sciences)
Organiser:
Prahladh Harsha
Date:
Monday, 11 Aug 2025, 17:30 to 18:30
Venue:
Homi Bhabha Auditorium
(Scan to add to calendar)
Abstract:
The need to trawl through massive amounts of data to see if it can reveal some interesting pattern is overwhelming all sciences. A massive amount of time and computing resources are often expended looking for patterns in data that have nothing to reveal. In modern times, even expressing the "pattern" that has been found takes enormous amounts of time. Is it possible to run quick and dirty tests on data to see if it even contains a pattern of interest, before actually learning the entire pattern (if one exists)?
The field of Property Testing studies exactly this problem—searching for algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property. It was initiated by an accidental discovery by Blum, Luby and Rubinfeld in the late 1980s showing that some complex properties could be tested remarkably efficiently. In the four decades since the original discovery, the scope of Property Testing has expanded broadly—covering properties of algebraic, graph-theoretic, statistical, and functional nature; and the resulting techniques have connected the field to combinatorics, additive number theory, harmonic analysis, algebraic geometry, while having applications in complexity theory, combinatorial optimization and even extremal graph theory.
In this talk, I will briefly survey some of these results before focussing on two celebrated results within this field: (1) linearity testing: testing if a multivariate function is actually linear, in constant time independent of the number of variables! And (2) Low-degree testing: extending linearity testing to higher degree polynomials. Time permitting, I will mention a recent result with collaborators Prahladh Harsha, Mrinal Kumar and Ramprasad Saptharishi (all from TIFR!), giving the ultimate dimension reduction result for low-degree testing.
SPEAKER INFORMATION: Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, where he has been since 2015. He is a recipient of the Nevanlinna Prize, the Infosys Foundation Prize, and the IEEE Hamming Medal. His research interests revolve around mathematical studies of communication and computation.
| Speaker: | Madhu Sudan (Harvard John A. Poulson School of Engineering and Applied Sciences) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 11 Aug 2025, 17:30 to 18:30 |
| Venue: | Homi Bhabha Auditorium |
(Scan to add to calendar)
Abstract:
The need to trawl through massive amounts of data to see if it can reveal some interesting pattern is overwhelming all sciences. A massive amount of time and computing resources are often expended looking for patterns in data that have nothing to reveal. In modern times, even expressing the "pattern" that has been found takes enormous amounts of time. Is it possible to run quick and dirty tests on data to see if it even contains a pattern of interest, before actually learning the entire pattern (if one exists)?
The field of Property Testing studies exactly this problem—searching for algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property. It was initiated by an accidental discovery by Blum, Luby and Rubinfeld in the late 1980s showing that some complex properties could be tested remarkably efficiently. In the four decades since the original discovery, the scope of Property Testing has expanded broadly—covering properties of algebraic, graph-theoretic, statistical, and functional nature; and the resulting techniques have connected the field to combinatorics, additive number theory, harmonic analysis, algebraic geometry, while having applications in complexity theory, combinatorial optimization and even extremal graph theory.
In this talk, I will briefly survey some of these results before focussing on two celebrated results within this field: (1) linearity testing: testing if a multivariate function is actually linear, in constant time independent of the number of variables! And (2) Low-degree testing: extending linearity testing to higher degree polynomials. Time permitting, I will mention a recent result with collaborators Prahladh Harsha, Mrinal Kumar and Ramprasad Saptharishi (all from TIFR!), giving the ultimate dimension reduction result for low-degree testing.
The field of Property Testing studies exactly this problem—searching for algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property. It was initiated by an accidental discovery by Blum, Luby and Rubinfeld in the late 1980s showing that some complex properties could be tested remarkably efficiently. In the four decades since the original discovery, the scope of Property Testing has expanded broadly—covering properties of algebraic, graph-theoretic, statistical, and functional nature; and the resulting techniques have connected the field to combinatorics, additive number theory, harmonic analysis, algebraic geometry, while having applications in complexity theory, combinatorial optimization and even extremal graph theory.
In this talk, I will briefly survey some of these results before focussing on two celebrated results within this field: (1) linearity testing: testing if a multivariate function is actually linear, in constant time independent of the number of variables! And (2) Low-degree testing: extending linearity testing to higher degree polynomials. Time permitting, I will mention a recent result with collaborators Prahladh Harsha, Mrinal Kumar and Ramprasad Saptharishi (all from TIFR!), giving the ultimate dimension reduction result for low-degree testing.
SPEAKER INFORMATION: Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, where he has been since 2015. He is a recipient of the Nevanlinna Prize, the Infosys Foundation Prize, and the IEEE Hamming Medal. His research interests revolve around mathematical studies of communication and computation.