Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Non-Interactive Simulation:
TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

TR17-125 | 7th August 2017
Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Dimension Reduction for Polynomials over Gaussian Space and Applications

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

ISSN 1433-8092 | Imprint