[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~
Date:         Tuesday, May 15,  2012
Time:        3 p.m.
Place:        Ryerson 251, 1100 E. 58th Street
_________________________ 

Speaker:    Alexandra Kolla
From:        UIUC
Title:         Maximal Inequality for Spherical Means on the Hypercube
Abstract:   In this talk, we establish a dimension-free ell_2 maximal inequality for spherical means on the Hypercube graph {0,1}^n. 
Combinatorially, this inequality implies the following stronger alternative to the union-bound technique: Assume that we have a binary function f (values 0,1) on the n-dimensional hypercube Hn, with N=2^n vertices. Think of the set X={x\in Hn : f(x)=1} as the set vertices that a malicious adversary "spoils". Assume |X|<\epsilon N, i.e. the adversary can only spoil up to \epsilon fraction of the vertices. Fix a threshold \lambda>\epsilon. Say a (hamming) sphere S(x,r) or radius r around a point x is "bad" if the adversary has spoiled more than \lambda fraction of the points in the shpere. We call a point x "ruined" if *there exists* a radius  r for which the sphere S(x,r) around x is bad. Our maximal inequality implies that for every \lambda, there is an absolute constant \epsilon (which does not depend on the dimension n) that if the adversary spoils at most \epsilon fraction of the points then the "ruined" set is a strict subset of the hypercube. Note that applying a union-bound over radii instead, we would not get any useful inequality for the size of the ruined set.

Joint work with Aram Harrow (UW) and Leonard Schulman (Caltech).

*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/20120515/5a4e2d0d/attachment.htm