Elchanan Mossel

Elchanan Mossel

orcid

Research Focus & Metrics

Academic Career Length

29Years (1998-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
25 November 2013 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Closed access
PDF file
FKFlorent Krzakala
Florent Krzakala
CMCristopher Moore
Cristopher Moore
EMElchanan Mossel
Elchanan Mossel
JNJoe Neeman
Joe Neeman
ASAllan Sly
Allan Sly
PZPan Zhang
Pan Zhang
Significance: Spectral algorithms are widely applied to data clustering problems, including finding communities or partitions in graphs and networks. We propose a way of encoding sparse data using a “nonbacktracking” matrix, and show that the corresponding spectral algorithm performs optimally for some popular generative models, including the stochastic block model. This is in contrast with classical spectral algorithms, based on the adjacency matrix, random walk matrix, and graph Laplacian, which perform poorly in the sparse case, failing significantly above a recently discovered phase transition for the detectability of communities. Further support for the method is provided by experiments on real networks as well as by theoretical arguments and analogies from probability theory, statistical physics, and the theory of random matrices.

1 January 2007 in SIAM Journal on Computing
Verified
Journal Article
Closed access
SKSubhash Khot
Subhash Khot
GKGuy Kindler
Guy Kindler
EMElchanan Mossel
Elchanan Mossel
RORyan O’dOnnell
Ryan O’dOnnell
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX‐CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if the Unique Games Conjecture of Khot in [Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] holds, then the Goemans–Williamson approximation algorithm is optimal. Our result indicates that the geometric nature of the Goemans–Williamson algorithm might be intrinsic to the MAX‐CUT problem. Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30]. A stronger version of this conjecture called Plurality Is Stablest is still open, although [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30] contains a proof of an asymptotic version of it. Our techniques extend to several other two‐variable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX‐2SAT, MAX‐q‐CUT, and MAX‐2LIN(q). For MAX‐2SAT we show approximation hardness up to a factor of roughly $.943$. This nearly matches the $.940$ approximation algorithm of Lewin, Livnat, and Zwick in [Proceedings of the 9th Annual Conference on Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, 2002, pp. 67–82]. Furthermore, we show that our .943... factor is actually tight for a slightly restricted version of MAX‐2SAT. For MAX‐q‐CUT we show a hardness factor which asymptotically (for large q) matches the approximation factor achieved by Frieze and Jerrum [Improved approximation algorithms for MAX k‐CUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, pp. 1–13], namely $1 - 1/q + 2({\rm ln}\,q)/q^2$. For MAX‐2LIN(q) we show hardness of distinguishing between instances which are $(1-\epsilon)$‐satisfiable and those which are not even, roughly, $(q^{-\epsilon/2})$‐satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev [Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 205–214]. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\epsilon$ vs. ε hardness for MAX‐2LIN(q) is equivalent to the Unique Games Conjecture.

14 August 2017 in Combinatorica
Verified
Journal Article
Closed access
PDF file
EMElchanan Mossel
Elchanan Mossel
JNJoe Neeman
Joe Neeman
ASAllan Sly
Allan Sly

20 July 2014 in Probability Theory and Related Fields
Verified
Journal Article
Open access
PDF file
EMElchanan Mossel
Elchanan Mossel
JNJoe Neeman
Joe Neeman
ASAllan Sly
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, and computer science. In its simplest form, the planted partition model is a model for random graphs on \(n\) nodes with two equal-sized clusters, with an between-class edge probability of \(q\) and a within-class edge probability of \(p\) . Although most of the literature on this model has focused on the case of increasing degrees (ie. \(pn, qn \rightarrow \infty \) as \(n \rightarrow \infty \) ), the sparse case \(p, q = O(1/n)\) is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if \(p = a/n\) and \(q = b/n\) , then Decelle et al. conjectured that it is possible to cluster in a way correlated with the true partition if \((a - b)^2 > 2(a + b)\) , and impossible if \((a - b)^2 < 2(a + b)\) . By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if \((a - b)^2 > C (a + b)\) for some sufficiently large \(C\) . We prove half of their prediction, showing that it is indeed impossible to cluster if \((a - b)^2 < 2(a + b)\) . Furthermore we show that it is impossible even to estimate the model parameters from the graph when \((a - b)^2 < 2(a + b)\) ; on the other hand, we provide a simple and efficient algorithm for estimating \(a\) and \(b\) when \((a - b)^2 > 2(a + b)\) . Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.

17 May 2004
Verified
Conference Paper
Open access
PDF file
RLR. J. Lipton
R. J. Lipton
EME. Markakis
E. Markakis
EMElchanan Mossel
Elchanan Mossel
ASA. Saberi
A. Saberi

17 March 2010 in Annals of Mathematics
Verified
Journal Article
Closed access
EMElchanan Mossel
Elchanan Mossel
RORyan O’donnell
Ryan O’donnell
KOKrzysztof Oleszkiewicz
Krzysztof Oleszkiewicz