Program

Speaker: Dimitris Achlioptas, UCSC Title: Random Constraint Satisfaction Problems: From Physics to Algorithms For a number of random constraint satisfaction problems, such as random k-SAT and random graph coloring, we now have excellent estimates of the largest constraints-to-variables ratio for which they have solutions. These estimates imply that all known polynomial- time algorithms stop finding solutions much before solutions cease to exist. To understand the origin of this phenomenon we study the evolution of the structure of the space of solutions in random CSPs as constraints are added. In particular, we will survey both what physicists hypothesize happens in this evolution, and what has been rigorously proven so far. We will see that the rigorous results are both in agreement with the physics predictions and help demystify Survey Propagation, an extremely successful heuristic proposed by physicists for random CSPs.

Speaker: Chen Avin, Ben Gurion U Title: Random Walks Techniques in Networking In recent years random-walk-based algorithms have been proposed for a variety of networking tasks. These proposals include searching, routing, self-stabilization, and query processing in wireless networks, peer-to-peer networks and other distributed systems. This approach is gaining popularity since random walks present locality, simplicity, low-overhead and inherent robustness to structural changes. Two properties of the random walk on graphs are essential to determine the efficiency of this approach: cover time (the expected time to visit all nodes) and mixing time (the time to sample a node uniformly). In this talk I will present some of my work on the topic, including: 1.) The cover time and mixing time of a simple model of random wireless network (i.e random geometric graphs). 2.) Enhancing random walk efficiency by implementing the power of 2 choice into the walk. 3.) Some in-progress work (to be announced later).

Speaker: Vladimir Chernyak, Wyane State Title: Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower Loop Calculus introduced in [Chertkov, Chernyak '06] constitutes a new theoretical tool that explicitly expresses the symbol Maximum A Posteriori (MAP) solution of a general statistical inference problem via a solution of the Belief Propagation (BP) equations. This finding brought a new significance to the BP concept, which in the past was thought of as just a loop-free approximation. In this talk we continue a discussion of the Loop Calculus. We introduce an invariant formulation which helps to generalize the Loop Calculus approach to a q-are alphabet.

Speaker: Aaron Clauset, Santa Fe Institute Title: Seeing Past the Hype: Making Power-Law Distributions Useful Again Power-law distributed quantities are ubiquitous in the physics of complex systems, being at the heart of many quite general mechanisms. And yet, the statistical methods used in physics to infer or estimate power-law behavior from actual data are ad hoc, subjective, and often highly biased. Further, such power-law models are rarely validated in any strong sense of the word. In this talk, I first discuss the problems with current methods for fitting and testing power-law models of distributions. Then, I summarize a new inference framework for dealing with heavy-tailed data that is principled, objective, and accurate. In closing, I briefly reconsider, using these new tools, 25 data sets and their previously conjectured power-law distributions. And, far from being the end of the modeling phase, I show that a careful comparison with a power-law model can generate useful new hypotheses for future investigation.

Speaker: Ashish Goel, Stanford Title: Sampling, aggregation, and phase transitions in sensor networks Unlike data networks, the connectivity of sensor networks is largely dictated by spatial proximity. This makes grids and random geometric graphs good idealized models for sensor networks, and often results in simpler algorithms and stronger properties. We will explore three problems along this general theme. (a) Phase transitions: We show that all monotone graph properties undergo sharp phase transitions in geometric random graphs as the radius of communication increases. This settles a conjecture of Krishnamachari et al and McColm. The phase transitions in geometric random graphs are both much sharper and much stronger than for Bernoulli random graphs. (b) Aggregating spatially correlated data: We present a simple randomized process for aggregating spatially correlated data (in an N x N grid) as it travels to a central collection agent. The aggregation tree we construct is within a constant factor of the optimum, regardless of the scale of correlation. (c) Multi-scale sampling: We present a scheme whereby any sensor node (in an N x N grid) can approximately answer moment and quantile queries about any rectangular region which contains the node. No communication is required at query-time. During the pre-processing phase, each node essentially draws K independent samples from all surrounding rectangular regions while performing only O(K log^2 N) transmissions.Part (a) represents joint work with Rai and Krishnamachari. Part (b) represents joint work with Enachescu, Govindan, and Motwani.

Speaker: Vicenç Gómez, U of Pompeu Fabra Title: Truncating the Loop Series Expansion for Belief Propagation Recently, M. Chertkov and V.Y. Chernyak derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the Belief Propagation solution. By adding correction terms to the BP free energy, one for each "generalized loop" in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce Truncated Loop Series BP (TLSBP), a particular way of truncating the loop series of M. Chertkov and V.Y. Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model, regular random graphs and on Promedas, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered.

Speaker: Hasan Guclu, LANL Title: Task-Based Synchronization in Complex Noisy Networks We study the statistics and scaling of fluctuations in noisy task-completion landscapes, such as those emerging in synchronized distributed-computing networks, or generic causally-constrained queuing networks. For small-world and scale-free networks the average size of the fluctuations becomes finite (synchronized state) and the extreme fluctuations typically diverge at most logarithmically in the large system-size limit ensuring synchronization in a practical sense. Provided that local fluctuations in the network are short-tailed, the statistics of the extremes are governed by the Gumbel distribution.

Speaker: Thomas Halford, USC Title: Improving Belief Propagation via Graphical Model Transformation It is now well-known that belief propagation (BP) results in exact inference algorithms on cycle-free graphical models and inexact, yet often substantially less complex, inference algorithms on graphical models with cycles. A number of approaches have been taken to improving the performance of BP for the latter case. Yedidia et al. considered generalizations of BP acting on regions of the original graph. Motivated by statistical physics, Chernyak and Chertkov introduced the loop calculus approach. Both of these methodologies can be viewed as applying a non-standard BP algorithm to a standard graphical model. In this talk, an alternative approach is described in the context of graphical models for codes. Specifically, we consider the application of the standard BP algorithm to non-standard models. In order to derive such non-standard models, we introduce a set of graphical model transformations which is shown to span the space of all models for a given fixed code. These transformations thus enable the search for non-standard models to be formalized in the language of combinatorial optimization. The efficacy of this approach is demonstrated via simulation. We conclude with a discussion of the relationships between model transformation, generalizations of BP, and the loop calculus.

Speaker: Matthew Hastings, LANL Title: Community Detection and Clustering as Inference Problems Community detection is a well-studied problem with applications to biological, social, and other networks. Remarkably, however, there is no good definition of this problem. In this talk, we show that one of the standard tests of community detection algorithms, the "four groups" test due to Newman and Girvan, provides a precise definition of community detection as a problem in Bayesian inference. We then apply techniques used for other Bayesian inference problems, in particular the belief propagation algorithm developed for decoding error-correcting codes in communication over a noisy channel, to develop a very accurate and fast community detection algorithm. We then apply related techniques to similar problems such as data clustering.

Speaker: Ralf Koetter, TU München Title: Random Network Coding for Errors and Erasures We consider the problem of organizing multicast and unicast connections in a network. Random network coding is by now a well understood formalism for this task. We address the problem of erroneous, undetected errors and erasures. We show how coding schemes in the Grassmannian graph are a natural approach to address the arising problems.

Speaker: Bhaskar Krishnamachari, USC Title: Querying Sensor Networks Wireless ad hoc sensor networks can be viewed as distributed databases where information about significant events are stored within the network and retrieved through queries. We present a few case studies concerning the design and analysis of structured and unstructured querying techniques for these networks. These include fundamental scaling laws for querying, comparison of different push-pull schemes, and some interesting enhancements of the simple random walk for efficient querying.

Speaker: Lukas Kroc, Cornell Title: Empirical validation of the relationship between Survey Propagation and covers in random 3-SAT It was recently shown that Survey Propagation (SP) can be viewed as a form of belief propagation, computing marginal probabilities over certain objects called covers of a formula. However, the existence of these objects in random 3-SAT formulas has not been proved yet, and initial empirical evidence has suggested that covers may not even exist in large such formulas. In this work, we perform a detailed empirical study of covers in random 3-SAT, obtaining evidence suggesting that such covers do exist even for large formulas, albeit they are hard to find using traditional SAT techniques. Moreover, despite the loopiness of the formulas, SP is surprisingly accurate at computing marginals over these covers. This reopens the possibility that SP\'s remarkable success on random 3-SAT can be attributed to effects analogous to those in random k-SAT for higher values of k, where the situation is much better understood (namely, in terms of covers).

Speaker: Muriel Médard, MIT Title: Some Interesting Directions in Network Coding Network coding has been shown to be beneficial in terms of throughput for networks. However, the interplay between theory and practice depends not only on improved throughput performance but also on ease of algorithmic implementation, impact on other performance measures and interaction with existing systems. In this talk, we overview some of the algorithmic issues concerning network coding, such as distributed optimization in multicast systems and choice of network codes in non-multicast scenarios. We also address issues of delay and robustness in network coded systems. We propose some new algorithmic directions for network coding and discuss their potential impact on performance.

Speaker: Marc Mezard, CNRS & Universite Paris Sud Title: Information Broadcast on a Tree: The Reconstruction Problem Consider a tree network whose links correspond to noisy communication channels. An information source generates a symbol at the root of the tree and broadcasts it through the network. The reconstruction problem asks whether the information received at the leaves allows to reconstruct the symbol which was transmitted. In the large system limit, there is a phase transition: reconstruction is possible only when the channel noise is smaller than a threshold. This talk shows that the reconstruction threshold coincides with the dynamical glass transition for an associated statistical physics problem. This correspondence allows to derive a number of new results for reconstruction. It also sheds some new light on glass transitions.

Speakers: Sanjoy Mitter, MIT and Nigel Newton, U of Essex & MIT Title: A Variational View of Statistical Inference and Channel Coding In the 60 or so years since Shannon's noisy channel coding theorem a number of papers have been published on its connections with statistical mechanics. A common feature of these is that the phenomenon of channel capacity is viewed as a type of phase transition. The talk will develop these ideas, but in the framework of Bayesian inference. This admits a variational form, in which the posterior distribution minimises an information quantity we call the 'apparent information'. The variational formulation can be extended to infinite systems, where it shares many of the properties of the Gibbs variational principle. We shall consider a number of estimation problems associated with the noisy channel coding theorem, and show that connections between the specific apparent information quantities in the different layers of the communication architecture are at its heart. The specific apparent information quantities for these problems exhibit a variety of phase transitions. We give preliminary results on the existence and nature of 'Gibbs' measures in this context. Standard results on their existence and uniqueness, requiring translation invariance, are not applicable here. The broader conceptual goal of our research is to understand statistical mechanics where observations are explicitly modeled, and to view statistical inference of the 'state' given 'observations' as a problem of interactive statistical mechanics. We believe that there are nontrivial connections between recent work on nonequilibrium statistical mechanics (Gallavotti, Ruelle, Lebowitz) and statistical inference. We have shown that these connections are quite precise in the context of observed diffusion processes. Generalizations of work on decay of correlations and correlation inequalities (for example, GKS inequalities) to the context of statistical inference are challenging problems whose investigation would lead to a deeper connection between statistical physics and statistical inference.

Speaker: Andrea Montanari, Stanford Title: Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space (the set of assignments). I will consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs), and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states ("clusters"), and subsequently condensates over the largest such states. I will discuss the nature and location of these phase transitions, as well as their algorithmic implications.

Speaker: Cristopher Moore, University of New Mexico & Santa Fe Institute Title: Inferring Hierarchical Structure and Predicting Missing Links Many real-world networks appear to have a hierarchical structure, containing communities and subcommunities at many different scales. These could correspond to interest groups on the Web, functional units in a metabolism, or ecological communities in a food web. We present a mathematically principled way to infer these structures from real-world network data; specifically, we use a Markov chain Monte Carlo algorithm to sample hierarchical structures with probability proportional to the likelihood with which they would generate the observed connections. Our method does much more than simply clustering the network: instead, it automatically detects both assortative and disassortative behavior at all scales of organization. Moreover, it allows us to rate how "surprising" a given connection is, and it performs far better than chance if we use it to predict connections that have not yet been observed. It may therefore be useful to experimenters for whom observing connections is costly. While this work is primarily experimental, it presents a number of interesting questions for theorists: how quickly does this Markov chain mix on different kinds of graphs? What can we say about network structure in a model where connections must be queried, rather than being observed all at once? Finally, what is it about real-world networks that makes these structures so important?

Speaker: Elchanan Mossel, UC Berkeley Title: Convergence of message passing algorithms on planted models: how and why? I will discuss the planted model for sat and recent results showing that message passing algorithms are effective for finding SAT assignments for such models. I will also address the problem of why this is interesting.

Speaker: Muthu Muthukrishnan, Rutgers & Google Title: Algorithmic Aspects of Sparse Approximation Problems The sparse approximation problem is to find the best linear combination of at most B vectors from a pre-specified dictionary of N dimensional vectors for a given input vector V, also of N dimensions. The classical versions arise from late 1700's with orthonormal dictionaries; the modern versions have richer dictionaries, weighted norms or study compressed sensing. This talk will focus on algorithmic results for such problems.

Speaker: Eli Ben-Naim, LANL Title: How to Chose a Champion League competition is investigated using random processes and scaling techniques. In our model, a weak team can upset a strong team with a fixed probability. Teams play an equal number of head-to-head matches and the team with the largest number of wins is declared to be the champion. The total number of games needed for the best team to win the championship with high certainty, T, grows as the cube of the number of teams, N, i.e., T ~ N^3. This number can be substantially reduced using preliminary rounds where teams play a small number of games and subsequently, only the top teams advance to the next round. When there are k rounds, the total number of games needed for the best team to emerge as champion, T_k, scales as follows, T_k ~N^(\gamma_k) with gamma_k=1/[1-(2/3)^(k+1)]. For example, gamma_k=9/5,27/19,81/65 for k=1,2,3. These results suggest an algorithm for how to infer the best team using a schedule that is linear in N. We conclude that league format is an ineffective method of determining the best team, and that sequential elimination from the bottom up is fair and efficient.

Speaker: Nandakishore Santhi, LANL Title: The Secant Method Decoder Several efficient near optimal decoding methods have been proposed in recent times for low density parity check codes. Most of these decoding methods are related to the belief-propagation technique on graphs with loops, pioneered by Gallager in the 1950s. These decoders can also be understood in terms of linear programming. In this paper we discuss a completely different decoder based on an iterative non-linear minimization technique also from the 1950s. We consider the recovery of binary coded messages corrupted by noise on a BSC channel. We form a system of non-linear equations whose solution is the desired codeword estimate. This system is then solved using a modified multi-dimensional secant method which can be shown to have a local rate of convergence equal to the golden-ratio. We will present experimental results for typical binary codes.

Speaker: Devavrat Shah, MIT Title: Max-product for Maximum Weight Independent Set Given a graph G=(V,E), an independent set I is a subset of V such that no two vertexes in I are connected in G. When vertexes of G are assigned weights, the weight of I is the sum of weights of vertexes in it. The question of finding an independent set with the maximum weight arises in communication networks, distributed databases, parallel computation, etc. In these applications, algorithms are required to be distributed for architectural reasons. The max-product heuristic is by design distributed and iterative. The algorithm applied for max wt independent set is known to find a correct solution when G is a tree or "tree-like" with random (exponential) weights. However, it is not clear what happens when underlying graph has short cycles. In this talk, I will discuss the correctness and convergence of (a slightly modified asynchronous) max-product to find max. wt. independent set for any bipartite graph with arbitrary non-negative weights. These properties will be established by relating the max-product with an appropriate co-ordinate descent algorithm for the dual relaxation of integral linear program corresponding to the max. wt. independent set.

Speaker: Misha Stepanov, UofA Tucson Title: Dynamical stuctures in iterative decoding Standard iterative decoding of a graph based code does not guarantee convergence. For some codes decoded iteratively, as for the model [155,64,20] code considered, cycling of iterations is observed for lower weight configuration of the noise dominating the error floor asymptotic. The behavior of the iterative decoding near this special configuration is chaotic. As shown in [Stepanov, Chertkov'06] the iterative scheme can be improved to enforce the iteration convergence. We discuss in this talk how the decoding improvement affects the dangerous cycling configuration.

Speaker: Mohammad Hossein Taghavi, UCSD Title: Graph-Based Decoding in the Presence of ISI We present some recent results on a technique for approximating the maximum-likelihood (ML) detection in ISI channels based on linear programming (LP) or message passing (MP). In this method, we convert the detection problem into a binary decoding problem, which can be easily combined with LDPC decoding. We analyze the performance of LP-based detection in the absence of coding, and classify the ISI channels based on how LP detection performs on them. In particular, for a certain class of channels, uncoded LP detection provides the exact ML solution without an exponential complexity in the size of the channel memory, while for some other channels, this method has a non-diminishing probability of failure as SNR increases. We further present some simulation results, showing that while uncoded LP and MP detection methods have a similar behavior, in the presence of coding, MP significantly outperforms LP.

Speaker: Sekhar Tatikonda, Yale Title: Mixing and Clustering in Message-Passing Schemes The belief propagation algorithm and its variants have recently been shown to work quite well on hard constraint satisfaction problems. Survey propagation is one such algorithm that has been developed for solving the k-SAT problem. This algorithm is based on two hypotheses deriving from the replica symmetry breaking theory developed for the statistical mechanics of spin glasses. The first is that the solutions of constraint satisfaction problems near threshold organize into disjoint clusters. The second is that within each cluster there is spatial mixing. In this talk we show that both hypotheses hold for a large class of constraint satisfaction problems.

Speaker: David Tse, Wireless Foundations & UC Berkeley Title: Hierarchical Cooperation Achieves Optimal Capacity Scaling in Ad Hoc Networks n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart is subject to a power attenuation of r^{-\alpha} as well as a random phase. We identify exactly the scaling laws of the information theoretic capacity of the network. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales linearly with n. In the case of extended networks, where the density of nodes is fixed and the area increasing linearly with n, we show that the sum capacity scales as n^{2-\alpha/2} for \alpha <3 and \sqrt{n} for \alpha > 3. Thus, much better scaling than multihop can be achieved in dense networks, as well as in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed MIMO communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.

Speaker: Ruediger Urbanke, EPFL Title: How to Compute Scaling Parameters for Sparse Graph Codes Under Message-Passing Decoding with a Finite Message Alphabet Most new standards in communications contain iteratively decoded sparse graph codes to accomplish the error correction. To date there is a bewildering (and daily growing) list of candidate codes and an equally large list of decoders to choose from. How do we pick a good code from this list? For transmission over the binary erasure channel a scaling approach is known to lead to very good predictions on the error probability of codes for already moderate blocklengths. Such a scaling approach can therefore lead to efficient optimization techniques and can help in finding the best candidates. I will first discuss how to extend the scaling idea to general channels and general message-passing decoders with a finite message alphabet. This approach can be used in principle for any size of the message alphabet but its computational complexity grows like the sixth power. I will then briefly survey the steps that remain to be accomplished to convert this idea into a practical and efficient optimization tool. [This is joint work with J. Ezri, EPFL, and A. Montanari, Stanford.]

Speaker: Martin Wainwright, UC Berkeley Title: Probabilistic Analysis of LP Decoding We describe some recent results on the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of ``almost expansion'' in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients larger than the classical worst-case setting.

Speaker: Yair Weiss, HU Jerusalem Title: Linear Programming and Belief Propagation - Theory and Experiments I will briefly survey the surprising connection between max-product belief propagation and linear programming relaxations. In particular, I will show that this connection holds for a large number of belief propagation variants. I will then show how we have used this connection to solve hard problems in computer vision and computational biology.

Speaker: Dror Weitz, Tel-Aviv Title: Counting independent sets up to the tree threshold We present an exact tree representation for the marginal distribution at a vertex in binary-spin systems on general graphs. Our tree consists of the tree of self-avoiding walks starting at the relevant vertex together with an appropriate boundary condition imposed on a subset of the leaves. This novel representation allows us to identify the regular tree as the worst-case graph (among graphs with the same maximum degree) for Strong Spatial Mixing (a certain notion for decay of correlations with distance in the stationary distribution). In addition, if the spin system on the regular tree of degree D exhibits SSM (Strong Spatial Mixing), then using our tree representation we obtain a simple deterministic fully-polynomial approximation scheme for calculating the partition function of the spin system on all graphs of maximum degree D. Applying the above to the hard-core gas model (independent sets) with activity \lambda, and by establishing that this model on the regular tree of degree D exhibits SSM all the way up to the critical activity for uniqueness of the Gibbs measure (denoted \\lambda_c (D) ), we obtain the following two results: a) For all graphs $G$ of maximum degree D and for all \lambda < \lambda_c (D), the Gibbs measure of the hard-core model on G with activity \lambda is unique. This proves a conjecture posed by Alan Sokal, and extends the proven regime of uniqueness for many interesting graphs, including the square integer lattice Z^2. b) For any fixed D and for all \lambda < \lambda_c (D) there is a fully polynomial approximation scheme for the partition function of the hard-core model with activity \lambda on any graph of maximum degree D. This extends the regime of \lambda (as a function of D) for which an efficient approximation scheme is known to exist, and includes the interesting case of \\lambda=1 (all independent sets are equally weighted) and maximum degree D=5. If time permits, I will also mention some recent evidence suggesting that \lambda_c(D) is in fact the threshold for the algorithmic problem as well (i.e., that the latter bound for efficient approximation is tight).

Speaker: Jonathan Yedidia, Mitsubishi Research Title: Multi-cellular Logic Circuits I present a simple model of the underlying logic of multi-cellular organisms, and exploit the model to design multi-cellular logic circuits. In this model, an organism or circuit consists of a set of cells containing identical logic units. The logic units compute an output signal that is a fixed function of their input signals. Three kinds of signals are used: "factor" signals which target logic units in the same cell, "inter-cellular" signals which target logic units in neighboring cells, and "developmental" signals which either trigger developmental events like cell division, or are used to mark the results of developmental events. In the model, a logic circuit is always initialized as a single cell, and undergoes a developmental phase (to be simulated in software) until it reaches a fixed "adult" configuration, which can be implemented in hardware. The adult logic circuit consists of many identical cells, differing only in their history and neighbors, and should compute a desired input- output function. I give an example of the overall design strategy by presenting a multi-cellular logic circuit for a random-access memory.