[Colloquium] [Talks at TTIC] 5/8 Young Researcher Seminar Series: Pritish Kamath, MIT

[Alicia McClarin]

When:     Wednesday, May 8th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who:*       Pritish Kamath, MIT


*Title: *Non-Interactive Agreement and Dimension Reduction for Polynomials


*Abstract: *The ability to harness and work with randomness has been at the
heart of information theory and theoretical computer science. Of particular
interest to this talk is the use of randomness by a set of parties that are
spread out geographically. For example, randomness can enable such parties
to generate and share secrets.

The "Non-interactive Agreement Distillation" problem, specified by a joint
distribution P(x,y) and a target alphabet size k, is defined as follows:
Two players observe sequences (X_1, ... , X_n) and (Y_1, ... , Y_n)
respectively where {(X_i, Y_i)} are drawn i.i.d. from P(x,y). Both players
look at their share of randomness, and output an element of [k]. Their goal
is to maximize the probability that their outputs are the same, while
ensuring that their outputs are marginally uniform.

Given P(x,y) and k, what is the largest correlation (agreement probability)
that the players can achieve? It turns out that this value is not well
understood, even in some well motivated special cases. A priori, this value
is not even "computable", as there is no immediate upper bound on the
number of samples the players need to draw in order to achieve the best
possible correlation!

This talk will describe a recent line of work that obtains an explicit
bound on the number of samples needed to get \epsilon-close to the maximum
achievable correlation. At the heart of our result is a new technique that
we call "Dimension Reduction for Polynomials". It can be viewed as a
generalization of the well-known Johnson-Lindenstrauss lemma, which in this
context, corresponds to the special case of degree-1 polynomials. We
believe this technique could be of broader interest.

This talk will discuss the motivational aspects of the problem, its moral
and technical connections to other problems in theoretical computer science
and will mainly focus on the technique of "dimension reduction for
polynomials".

Based on joint works with Badih Ghazi, Prasad Raghavendra and Madhu Sudan. [
arXiv:1607.04322 <https://arxiv.org/abs/1607.04322>, arXiv:1708.03808
<https://arxiv.org/abs/1708.03808>]

*Host: *Nati Srebro <nati at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 510*
*Chicago, IL 60637*
*773-702-5370*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190501/eadaf3a1/attachment.html>