[Colloquium] Talks at TTIC: Li-Yang Tan, Columbia University

[Dawn Ellis]

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/20140402/69ea7063/attachment.htm