Combinatorial Statistics on Trees and Networks
Abstract
We have made substantial progress in a number of areas covered by the proposal. We have shown how to efficiently reconstruct order-based distributions from noisy comparisons and noisy orders thus providing important examples where the generating model is not a tree but can still be recovered efficiently. We have made some important discoveries on reconstruction of Markov random fields, essentially showing that Markov Random Fields of bounded degrees are reconstructive if the data at all nodes is observable and that the problem is computationally intractable if some nodes are hidden. For trees, we have studied a number of questions concerning aggregations of information from different sources, including mixtures of tree distributions and an analysis of gene trees and the corresponding population tree. We have continued studying optimization over networks, in particular, social networks. Our results concern optimization of spread processes, the structure of Nash Equilibrium in random games, efficient greedy learning in networks from Gaussian signals and the construction of optimal local compression graphs. Finally, we have made considerable progress in studying local algorithms for calculating marginal distributions over networks. Most importantly, we have shown that MCMC methods are applicable to graphs that are sparse on average. Indeed for the famous Ising model we have found the first tight conditions which ensure convergence.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 29, 2010
- Accession Number
- ADA531376
Entities
People
- Elchanan Mossel
Organizations
- University of California, Berkeley