The planted bisection model is a random graph in which the nodes are divided into two equal-sized communities and then edges added randomly way that depends on community membership. We establish necessary sufficient conditions for asymptotic recoverability of this model. When asymptotically recoverable, we give an efficient algorithm successfully recovers it. also show recoverable if only with high probability every node belongs to same as majority its neighbors.

The planted bisection model is a random graph in which the nodes are divided into two equal-sized communities and then edges added randomly way that depends on community membership. We establish necessary sufficient conditions for asymptotic recoverability of this model. When asymptotically recoverable, we give an efficient algorithm successfully recovers it. also show recoverable if only with high probability every node belongs to same as majority its neighbors. Our finding runs time almost...

We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ $b/n$ for inter- intra-block edge probabilities, respectively. It was recently shown that one can do better than a random guess if only $(a-b)^{2}>2(a+b)$. Using variant belief propagation, we give reconstruction algorithm is optimal in sense $(a-b)^{2}>C(a+b)$ some constant $C$ then our maximizes fraction nodes labeled correctly. Ours proven to achieve Along way, prove...

The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph that has been extensively studied in statistics, physics, and computer science. In its simplest form, for graphs on $n$ nodes with two equal-sized clusters, an between-class edge probability of $q$ within-class $p$. Although most literature this focused case increasing degrees (ie.\ $pn, qn \to \infty$ $n \infty$), sparse $p, q = O(1/n)$ interesting both from mathematical...

We prove the first robust dimension free isoperimetric result for standard Gaussian measure $\gamma_n$ and corresponding boundary $\gamma_n^+$ in $\mathbb {R}^n$. The main theory of isoperimetry (proven 1970s by Sudakov Tsirelson, independently Borell) states that if $\gamma_n(A)=1/2$ then surface area $A$ is bounded a half-space with same measure, $\gamma_n^+(A)\leq(2\pi)^{-1/2}$. Our results imply particular $A\subset \mathbb {R}^n$ satisfies $\gamma_n^+(A)\leq(2\pi)^{-1/2}+\delta$ there...

We prove that under the Gaussian measure, half-spaces are uniquely most noise stable sets. also a quantitative version of uniqueness, showing set which is almost optimally must be close to half-space. This extends theorem Borell, who proved same result but without and it answers question Ledoux, asked whether was possible Borell’s using direct semigroup argument. Our uniqueness has various applications in diverse fields.

In this paper we consider the collaborative ranking setting: a pool of users each provides small number pairwise preferences between $d$ possible items; from these need to predict for items they have not yet seen. We do so by fitting rank $r$ score matrix data, and provide two main contributions: (a) show that an algorithm based on convex optimization good generalization guarantees once user as few $O(r\log^2 d)$ comparisons -- essentially matching sample complexity required in related...

We establish the Gaussian Multi-Bubble Conjecture: least Gaussian-weighted perimeter way to decompose $\mathbb{R}^n$ into $q$ cells of prescribed (positive) measure when $2\le q\le n+1$, is use a ``simplicial cluster," obtained from Voronoi equidistant points. Moreover, we prove that simplicial clusters are unique isoperimetric minimizers (up null-sets). In particular, case $q=3$ confirms Double-Bubble $\mathbb{R}^n (n\ge 2)$ three tripod-cluster, whose interfaces consist half-hyperplanes...

We consider the problem of clustering (or reconstruction) in stochastic block model, regime where average degree is constant. For case two clusters with equal sizes, recent results by Mossel, Neeman and Sly, Massoulie, show that reconstructability undergoes a phase transition at Kesten-Stigum bound $λ_2^2 d = 1$, $λ_2$ second largest eigenvalue related matrix $d$ degree. In this paper, we address general more than and/or unbalanced cluster sizes. Our main result sufficient condition for to...

Recently, Kothari et al. gave an algorithm for testing the surface area of arbitrary set A ⊂ [0,1]n. Specifically, they a randomized such that if A's is less than S then will accept with high probability, and accepts probability there some perturbation at most κnS. Here, κn dimension-dependent constant which strictly larger 1 n ≥ 2, grows to 4/π as → ∞.

The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof the by induction on dimension discrete cube. Unlike previous proof, it uses neither "invariance principle" nor Borell's result Gaussian space. general enough to include all variants majority stablest such as "it ain't over until it's over" "Majority most predictable". Moreover, allows us derive constant level Sum Squares hierarchy. This implies particular that...

We establish the Gaussian Double-Bubble Conjecture: least Gaussian-weighted perimeter way to decompose $\mathbb{R}^n$ into three cells of prescribed (positive) measure is use a tripod-cluster, whose interfaces consist half-hyperplanes meeting along an $(n-2)$-dimensional plane at $120^{\circ}$ angles (forming tripod or "Y" shape in plane). Moreover, we prove that tripod-clusters are unique isoperimetric minimizers (up null-sets).

Suppose Alice and Bob receive strings X=(X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,...,X xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> ) Y=(Y ,...,Y each uniformly random in [s] <sup xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , but so that X Y are correlated. For symbol i, we have xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> =X with probability 1-ε otherwise is chosen independently from [s]. wish to use their...