Non-Interactive Agreement & Dimension Reduction for Polynomials
Speaker
Pritish Kamath
MIT
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
Title: Non-Interactive Agreement & Dimension Reduction for Polynomials
Abstract:
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, Alice and Bob, 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 (or agreement probability) that the players can achieve? In the special case where P(x,y) is the distribution of \rho-correlated Gaussians, the largest achievable correlation is also known as the "Optimal Noise-Stability of a k-partition" and has received wide interest in Computer Science. More generally, it is also related to the notions of common information studied in Information Theory.
It turns out that this value is not well understood, even in the special case of correlated Gaussians! Moreover, this value is a priori 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!
In this work, we obtain explicit (computable) bounds on the number of samples needed to get \epsilon-close to the maximum achievable correlation (or even for the more general problem of "non-interactive simulation"). This implies computability of the maximum achievable correlation. [Our bounds significantly improve upon the results obtained recently by De, Mossel & Neeman, using fundamentally different techniques.]
At the heart of our result is a new technique that we call "Dimension Reduction for Polynomials". It is analogous to the Johnson-Lindenstrauss lemma, which is a dimension reduction for vectors. This technique is mostly elementary, and we believe it to be of independent interest.
This talk will discuss the motivational aspects of the problem, its moral and technical connections to other problems in computer science and will mainly focus on the new technique of "dimension reduction for polynomials".
Based on joint works with Badih Ghazi, Prasad Raghavendra and Madhu Sudan.
https://eccc.weizmann.ac.il/report/2016/104/
https://eccc.weizmann.ac.il/report/2017/125/
Abstract:
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, Alice and Bob, 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 (or agreement probability) that the players can achieve? In the special case where P(x,y) is the distribution of \rho-correlated Gaussians, the largest achievable correlation is also known as the "Optimal Noise-Stability of a k-partition" and has received wide interest in Computer Science. More generally, it is also related to the notions of common information studied in Information Theory.
It turns out that this value is not well understood, even in the special case of correlated Gaussians! Moreover, this value is a priori 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!
In this work, we obtain explicit (computable) bounds on the number of samples needed to get \epsilon-close to the maximum achievable correlation (or even for the more general problem of "non-interactive simulation"). This implies computability of the maximum achievable correlation. [Our bounds significantly improve upon the results obtained recently by De, Mossel & Neeman, using fundamentally different techniques.]
At the heart of our result is a new technique that we call "Dimension Reduction for Polynomials". It is analogous to the Johnson-Lindenstrauss lemma, which is a dimension reduction for vectors. This technique is mostly elementary, and we believe it to be of independent interest.
This talk will discuss the motivational aspects of the problem, its moral and technical connections to other problems in computer science and will mainly focus on the new technique of "dimension reduction for polynomials".
Based on joint works with Badih Ghazi, Prasad Raghavendra and Madhu Sudan.
https://eccc.weizmann.ac.il/report/2016/104/
https://eccc.weizmann.ac.il/report/2017/125/