[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR

Tuesday, April 23, 2013
3:00 p.m.
Ryerson 251
 
Gabor Lippner
Harvard University
www.math.harvard.edu/~lippner
 
Title:  "Bounded degree parameter testing via measurable graphs."
 
Abstract:
Parameter testing studies which quantities can be approximated using randomized constant query complexity algorithms. In the case of bounded degree graphs, this is intimately connected with the notion of Benjamini-Schramm convergence. 
 
Gabor Elek observed that measurable graphs arise naturally as limit objects for Benjamini-Schramm convergent graphs sequences. I will describe a general pull-back method that uses this connection to translate results in measure theory to a combinatorial setting. It can be applied to give simple proofs of testability for various graph parameters, as well as to prove a regularity-lemma like decomposition theorem for bounded degree graphs.
 
Host: Prof. Laszlo Babai
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130417/784047fc/attachment.htm