BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1604
DTSTAMP:20250807T102227Z
SUMMARY:Testing for (algebraic) patterns in data
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Poulson School of Enginee
 ring and Applied Sciences)\n\nAbstract: \nThe need to trawl through massiv
 e amounts of data to see if it can reveal some interesting pattern is over
 whelming all sciences. A massive amount of time and computing resources ar
 e 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 le
 arning the entire pattern (if one exists)?The field of Property Testing st
 udies exactly this problem—searching for algorithms that Test if some (m
 assive) data satisfies some global Property without looking at all the dat
 a\, or inferring the parameters that explain how the data satisfies the pr
 operty. It was initiated by an accidental discovery by Blum\, Luby and Rub
 infeld in the late 1980s showing that some complex properties could be tes
 ted remarkably efficiently. In the four decades since the original discove
 ry\, the scope of Property Testing has expanded broadly—covering propert
 ies 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 ha
 ving applications in complexity theory\, combinatorial optimization and ev
 en extremal graph theory.In this talk\, I will briefly survey some of thes
 e 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-de
 gree testing: extending linearity testing to higher degree polynomials. Ti
 me 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.\n \nSPEA
 KER INFORMATION: Madhu Sudan is a Gordon McKay Professor in the John A. Pa
 ulson School of Engineering and Applied Sciences at Harvard University\, w
 here he has been since 2015. He is a recipient of the Nevanlinna Prize\, t
 he Infosys Foundation Prize\, and the IEEE Hamming Medal. His research int
 erests revolve around mathematical studies of communication and computatio
 n.\n \nTesting for (algebraic) patterns in data (August 11\, 2025) · Sci
 entific Talks (Indico)\nTIFR Institute Colloquium\n
URL:https://www.tcs.tifr.res.in/web/events/1604
DTSTART;TZID=Asia/Kolkata:20250811T173000
DTEND;TZID=Asia/Kolkata:20250811T183000
LOCATION:Homi Bhabha Auditorium
END:VEVENT
END:VCALENDAR