[Colloquium] REMINDER: Talks at TTIC: Li-Yang Tan, Columbia University
Dawn Ellis
dellis at ttic.edu
Tue Apr 8 15:20:40 CDT 2014
When: Wednesday, April 9th at 11am
Where: TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526
Speaker: Li-Yang Tan, Columbia University
Title: Structure theorems, analytic methods, and algorithmic
applications
Abstract: I will describe work I have done using analytic/continuous
methods -- invariance principles, hypercontractive inequalities, and limit
theorems -- to prove structural theorems about basic discrete objects:
Boolean functions, graphs, and discrete distributions. These structural
theorems are leveraged to obtain computational results, both algorithmic
upper bounds and complexity-theoretic lower bounds, in various areas of
theoretical computer science. Specifically, I will describe three recent
results showing:
* (Property Testing) A polynomial lower bound on the well-studied problem
of monotonicity testing of Boolean functions, an exponential improvement on
the previous best bound from 2002. Our proof employs recently-developed
multidimensional central limit theorems to analyze the success probability
of property testing algorithms.
* (Optimization) The Lasserre semidefinite programming hierarchy
efficiently solves essentially all canonical hard instances of
Vertex-Cover. The key technical ingredient is an analytic proof of the
classical Frankl-Rodl theorem via the reverse hypercontractive inequality,
and a proof of this inequality in the sum-of-squares proof system.
* (Learning Theory) The first computationally efficient algorithm for
learning sums of independent integer-valued random variables, a natural
algorithmic problem in density estimation. To accomplish this, we build on
and extend existing results in probability theory to prove a new limit
theorem characterizing the structure of these distributions.
Based on joint works with Xi Chen, Costis Daskalakis, Ilias Diakonikolas,
Manuel Kauers, Ryan O'Donnell, Rocco Servedio, and Yuan Zhou.
Bio: Li-Yang Tan is a Ph.D. student at Columbia University, where he is
advised by Rocco Servedio. His research interests lie in theoretical
computer science, with a focus on discrete Fourier analysis, concrete
complexity, and computational learning theory.
Host: Julia Chuzhoy, cjulia at ttic.edu
--
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu
TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140408/56266f5a/attachment.htm
More information about the Colloquium
mailing list