text: We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for ( _ in - _ out > _ out e ) and fail for ( _ in - _ out < _ out e ) (with ( _ in ), ( _ out ) the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for ( _ in - _ out < _ out e ).
  @cite_35: For a number of random constraint satisfaction problems, such as random k-SAT and random graph hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems.
  @cite_14: Having trouble deciding which coding scheme to employ, how to design a new scheme, or how to improve an existing system? This summary of the state-of-the-art in iterative coding makes this decision more straightforward. With emphasis on the underlying theory, techniques to analyse and design practical iterative coding systems are presented. Using Gallager's original ensemble of LDPC codes, the basic concepts are extended for several general codes, including the practically important class of turbo codes. The simplicity of the binary erasure channel is exploited to develop analytical techniques and intuition, which are then applied to general channel models. A chapter on factor graphs helps to unify the important topics of information theory, coding and communication theory. Covering the most recent advances, this text is ideal for graduate students in electrical engineering and computer science, and practitioners. Additional resources, including instructor's solutions and figures, available online: www.cambridge.org 9780521852296.
  @cite_26: This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science discrete mathematics, and coding information theory. It is accessible to graduate students and researchers without a specific training in any of these fields. The selected topics include spin glasses, error correcting codes, satisfiability, and are central to each field. The approach focuses on large random instances, adopting a common probabilistic formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to study phase transitions.
  @cite_8: This paper studies the problem of detecting the presence of a small dense community planted in a large Erd o s-R 'enyi random graph @math , where the edge probability within the community exceeds @math by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size @math grows and the graph becomes sparser according to @math , there exists a critical value of @math , below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest @math -subgraph.
  @cite_40: 
  @cite_15: We study the planted ensemble of locked constraint satisfaction problems. We describe the connection between the random and planted ensembles. The use of the cavity method is combined with arguments from reconstruction on trees and the first and second moment considerations. Our main result is the location of the hard region in the planted ensemble. In a part of that hard region, instances have with high probability a single satisfying assignment.
  @cite_34: This paper studies a class of probabilistic models on graphs, where edge variables depend on incident node variables through a fixed probability kernel. The class includes planted constraint satisfaction problems (CSPs), as well as more general structures motivated by coding and community clustering problems. It is shown that under mild assumptions on the kernel and for sparse random graphs, the conditional entropy of the node variables given the edge variables concentrates around a deterministic threshold. This implies in particular the concentration of the number of solutions in a broad class of planted CSPs, the existence of a threshold function for the disassortative stochastic block model, and the proof of a conjecture on parity check codes. It also establishes new connections among coding, clustering and satisfiability.
summary: Let us mention that the very same phase transition structure arises in other inference problem, for instance in decoding sparse graph error correcting codes, or solving planted constraint satisfaction problems @cite_14 @cite_26 @cite_35 @cite_15 . A unified formalism for all of these problems is adopted in @cite_34 . All of these problems present a regime of model parameters whereby a large gap separates the optimal estimation accuracy, from the optimal accuracy achieved by known polynomial time algorithms. Establishing that such a gap cannot be closed under standard complexity-theoretic assumptions is an outstanding challenge. (See @cite_8 for partial evidence in this direction --albeit in a different regime.) One can nevertheless gain useful insight by studying classes of algorithms with increasing sophistication. This suggests that the principal eigenvector of @math should be localized on the set @math . Indeed this approach succeeds in the dense case (degree of order @math ), allowing to reconstruct @math with high probability @cite_40 .