Login
Talks & Seminars
Title: Property Testing and Affine-Invariance
Prof. Madhu Sudan, Harvard University
Date & Time: December 30, 2015 11:30
Venue: Ramanujan Hall, Department of Mathematics
Abstract:
Property testing considers the task of testing if a given function satisfies some nice property, *without* querying the function everywhere. Testing of algebraic properties in particular leads to extremely interesting mathematical questions, and the answers have had major consequences to theoretical computer science in the past two decades. The prototypical question here considers the task of testing if an m-variate function over a finite field is a polynomial of degree d. Whereas the number of coefficients specifying such a function could be exponentially large in minimum(m,d), one of the major results in the field shows that the number of queries needed to test this property is only linear in d (for sufficiently large fields). In these two lectures I will introduce an abstraction of the property of being a low-degree polynomial, namely "affine-invariance" - wherein the property being tested in closed under affine transformations of the domain. This abstraction presents a clean way to unify many results in the literature and strengthen and extend them. In the talks I will formally introduce affine-invariant properties, describe some structural results about affine-invariance and show some new affine-invariant properties that are denser than the class of low-degree polynomials. I will describe how the analysis of property tests is carried out in this abstract setting - strikingly the generality of the abstract setting forces the proofs to be simpler! I will conclude with a conjecture on the testability of affine-invariant properties. Based on joint works with many collaborators including Tali Kaufman, Elena Grigorescu, Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Noga Ron-Zewi, Alan Guo, Swastik Kopparty, and Elad Haramaty.
Speaker Profile:
Professor Madhu Sudan is from the Computer Science department at Harvard University. Professor Sudan has a large body of highly influential work in many areas of Theoretical Computer Science, including Error Correcting Codes, Probabilistically Checkable Proofs, and Property Testing. He has been the recipient of many awards, notably the Nevanlinna Prize awarded in 2002, and the Infosys Prize awarded in 2014. Professor Sudan has recently been offered the Jubilee Professorship by Indian Academy of Sciences. The distinguishing feature envisaged in this professorship is that students, teachers and researchers from India should draw maximum benefits and inspiration by their close interaction with Jubilee Professor. Professor R. K. Shyamsundar, CSE department, IIT Bombay, has been instrumental in coordinating this visit.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback