Publications (38)
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore, Joe Neeman +1
We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, consider the symmetric stochastic block m…
On extracting common random bits from correlated sources on large alphabets
Siu On Chan, Elchanan Mossel, Joe Neeman
Suppose Alice and Bob receive strings and each uniformly random in but so that and are correlated . For each symbol , we have…
Typical large graphs with given edge and triangle densities
Joe Neeman, Charles Radin, Lorenzo Sadun
The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermedia…
Junta correlation is testable
Anindya De, Elchanan Mossel, Joe Neeman
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a -Junta is testable.…
On the connectedness of a minimizing cluster's boundary
Emanuel Milman, Joe Neeman
We verify that an isoperimetric minimizing cluster on a simply connected homogeneous Riemannian manifold with at most one end always has connected boundary. In particular, the boun…
Noise Stability and Correlation with Half Spaces
Elchanan Mossel, Joe Neeman
Benjamini, Kalai and Schramm showed that a monotone function is noise stable if and only if it is correlated with a half-space (a set of the form $\{x…
Robust Optimality of Gaussian Noise Stability
Elchanan Mossel, Joe Neeman
We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almos…
Belief propagation, robust reconstruction and optimal recovery of block models
Elchanan Mossel, Joe Neeman, Allan Sly
We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities and for inter- and intra-block edge probabilities,…
Concentration Inequalities for Sums of Markov Dependent Random Matrices
Joe Neeman, Bobby Shi, Rachel Ward
We give Hoeffding and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix…
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel, Joe Neeman, Allan Sly
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the c…
Stochastic Block Models and Reconstruction
Elchanan Mossel, Joe Neeman, Allan Sly
The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics,…
Finding cliques using few probes
Uriel Feige, David Gamarnik, Joe Neeman +2
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an vertex graph, and need to output a clique. We show that if the input gr…
Nucleation during phase transitions in random networks
Joe Neeman, Charles Radin, Lorenzo Sadun
We analyze the 3-parameter family of random networks which are uniform on networks with fixed number of edges, triangles, and nodes (between 33 and 66). We find precursors of phase…
A law of large numbers for weighted plurality
Joe Neeman
Consider an election between k candidates in which each voter votes randomly (but not necessarily independently) and suppose that there is a single candidate that every voter prefe…
Is your function low-dimensional?
Anindya De, Elchanan Mossel, Joe Neeman
We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function a linear -junta if it is completely determ…
Plateau Bubbles and the Quintuple Bubble Theorem on
Emanuel Milman, Joe Neeman
Sullivan's multi-bubble isoperimetric conjectures in -dimensional Euclidean and spherical spaces assert that standard bubbles uniquely minimize total perimeter among all b…
The Gaussian Double-Bubble Conjecture
Emanuel Milman, Joe Neeman
We establish the Gaussian Double-Bubble Conjecture: the least Gaussian-weighted perimeter way to decompose into three cells of prescribed (positive) Gaussian measure…
Majority is Stablest : Discrete and SoS
Anindya De, Elchanan Mossel, Joe Neeman
The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by inducti…
An interpolation proof of Ehrhard's inequality
Joe Neeman, Grigoris Paouris
We prove Ehrhard's inequality using interpolation along the Ornstein-Uhlenbeck semi-group. We also provide an improved Jensen inequality for Gaussian variables that might be of ind…
A multidimensional version of noise stability
Joe Neeman
We give a multivariate generalization of Borell's noise stability theorem for Gaussian vectors. As a consequence we recover two inequalities, also due to Borell, for exit times of…
The Gaussian Double-Bubble and Multi-Bubble Conjectures
Emanuel Milman, Joe Neeman
We establish the Gaussian Multi-Bubble Conjecture: the least Gaussian-weighted perimeter way to decompose into cells of prescribed (positive) Gaussian measure wh…
Robust testing of low-dimensional functions
Anindya De, Elchanan Mossel, Joe Neeman
A natural problem in high-dimensional inference is to decide if a classifier depends on a small number of linear directions of its input data.…
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
Yeongwoo Hwang, Joe Neeman, Ojas Parekh +2
The Gaussian noise stability of a function is the expected value of over -correlated Gaussian random…
Standard Simplices and Pluralities are Not the Most Noise Stable
Steven Heilman, Elchanan Mossel, Joe Neeman
The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise…
Non interactive simulation of correlated distributions is decidable
Anindya De, Elchanan Mossel, Joe Neeman
A basic problem in information theory is the following: Let be an arbitrary distribution where the marginals and a…
The Structure of Isoperimetric Bubbles on and
Emanuel Milman, Joe Neeman
The multi-bubble isoperimetric conjecture in -dimensional Euclidean and spherical spaces from the 1990's asserts that standard bubbles uniquely minimize total perimeter among al…
A Proof Of The Block Model Threshold Conjecture
Elchanan Mossel, Joe Neeman, Allan Sly
We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph…
Spectral redemption: clustering sparse networks
Florent Krzakala, Cristopher Moore, Elchanan Mossel +4
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal,…
Majority Dynamics and Aggregation of Information in Social Networks
Elchanan Mossel, Joe Neeman, Omer Tamuz
Consider n individuals who, by popular vote, choose among q >= 2 alternatives, one of which is "better" than the others. Assume that each individual votes independently at random,…
Non-Reconstructability in the Stochastic Block Model
Joe Neeman, Praneeth Netrapalli
We consider the problem of clustering (or reconstruction) in the stochastic block model, in the regime where the average degree is constant. For the case of two clusters with equal…
Testing surface area with arbitrary accuracy
Joe Neeman
Recently, Kothari et al.\ gave an algorithm for testing the surface area of an arbitrary set . Specifically, they gave a randomized algorithm such that if 's…
Moderate Deviations in Cycle Count
Joe Neeman, Charles Radin, Lorenzo Sadun
We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $\calG(n, m)$ random graph. We show that the probability of decreasing triangle density by $…
The Search Problem in Mixture Models
Avik Ray, Joe Neeman, Sujay Sanghavi +1
We consider the task of learning the parameters of a {\em single} component of a mixture model, for the case when we are given {\em side information} about that component, we call…
Lipschitz changes of variables via heat flow
Joe Neeman
We extend Caffarelli's contraction theorem, by proving that there exists a Lipschitz changes of variables between the Gaussian measure and certain perturbations of it. Our approach…
Existence of a symmetric bipodal phase in the edge-triangle model
Joe Neeman, Charles Radin, Lorenzo Sadun
In the edge-triangle model with edge density close to 1/2 and triangle density below 1/8 we prove that the unique entropy-maximizing graphon is symmetric bipodal. We also prove tha…
Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons
Dohyung Park, Joe Neeman, Jin Zhang +2
In this paper we consider the collaborative ranking setting: a pool of users each provides a small number of pairwise preferences between possible items; from these we need to…
Noise Stability is computable and low dimensional
Anindya De, Elchanan Mossel, Joe Neeman
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 a…
Robust dimension free isoperimetry in Gaussian space
Elchanan Mossel, Joe Neeman
We prove the first robust dimension free isoperimetric result for the standard Gaussian measure and the corresponding boundary measure $γ_n^+$ in . The main…