Name
Abstract | ||
|---|---|---|
Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of $mathbb{R}^n$ for $n geq 1$ to $k$ parts with given Gaussian measures $mu_1,ldots,mu_k$. call a partition $epsilon$-optimal, if its noise stability is optimal up to an additive $epsilon$. In this paper we address the following questions: (i) Can an $epsilon$-optimal partition be found in an explicit bounded dimension $n(epsilon)$? (ii) Is such an $epsilon$- partition computable? We provide an affirmative answer to both questions. Our results show that approximately most stable voting schemes can be computed efficiently and also imply a generalization of recent results by Ghazi, Kamath and Sudan on the decidability of non-interactive simulation of joint distributions. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Probability | Discrete mathematics,Noise stability,Combinatorics,Hardness of approximation,Computability,Gaussian,Partition (number theory),Mathematics,Computable function |
DocType | Volume | Citations |
Journal | abs/1701.01483 | 2 |
PageRank | References | Authors |
0.42 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anindya De | 1 | 239 | 24.77 |
| Elchanan Mossel | 2 | 1725 | 145.16 |
| Joe Neeman | 3 | 254 | 14.51 |