Theory Lunch Seminar

Wednesday, February 3, 2016 -
12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates & Hillman Centers

Speaker:

YU ZHAO, Ph.D. Student http://www.cs.cmu.edu/~yuzhao1/

Event Website:

http://www.cs.cmu.edu/~theorylunch/20160203.html

For More Information, Contact:

nhaghtal @ cs.cmu.edu

Let  f(x_1, ..., x_n) be an n-variate real multilinear polynomial of degree at most k.  For its one-block decoupled version f~, we show tail-bound comparisons of the form Pr[ |f~(y, z)|  > C_k t] t ]
Our constants C_k, D_k are significantly better than those known for ''full decoupling''. For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, y, z are {+1, -1} random variables we obtain C_k = O(k^2),  D_k = k^{O(k)}.  By contrast, for full decoupling only C_k = D_k = k^{O(k)} is known in these settings.

We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO~Inequality).


Yu Zhao is a PhD candidate at Carnegie Mellon University advised by Ryan O'Donnell. Previously, he completed M.S. in Carnegie Mellon University and Bachelor in Computer Science in Tsinghua University. His research interests include complexity and analysis of boolean functions.
Supported in part by Yahoo! Labs and the Simons Foundation.

Keywords:

Seminar Series