[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

     ~REMINDER~

COMPUTER SCIENCE

The University of Chicago

THEORY SEMINAR

___________________

Date: 	Tuesday, October 18, 2011

Time:	3 p.m.

Place: Ryerson 251, 1100 E. 58th Street

_____________________

Speaker:	Madhu Sudan

From:		Microsoft Research

Web page:	cs.uiuc.edu/~madhu

Title:		Invariance in Property Testing
 

Abstract: The goal of Property Testing is to design highly efficient algorithms

that sample very small portions of massive data to detect if the data

satisfies some global property. As ambitious as this goal may sound,

research in the past two decades has shown that a wide variety of

properties, looking for statistical, combinatorial, graph-theoretic,

or algebraic structure in data, can be tested surprisingly efficiently.

In this talk we will explain how the ``invariance'' of the property has

played a role, mostly implicitly and recently explicitly, in the success

of property testing. 

 

A property is said to be invariant under a permutation pi if permuting

the data points by this permutation leaves the property unchanged. The

set of permutations that keep a property invariant forms a group under

composition, and many of the above different themes in property testing

can be classified based on the invariant group of the property. In this

talk we stress in particular the role of the affine group on vector

spaces (or a large field) in the testing of algebraic properties. 

 

Based on works of/with: Tali Kaufman, Shachar Lovett, Eli Ben-Sasson, Elena

Grigorescu, Ghid Maatouk and Amir Shpilka.

 

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

Persons who need assistance should call 773-702-6614


_______________________________________________
Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
_______________________________________________
staff mailing list  -  staff at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/staff
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111018/585dbcb6/attachment.htm