Analysis of low-density codes and improved designs using irregular graphs

We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the analysis of several previously studied random processes of interest, includingrandom loss-resilient codes, solving random k-SAT formula using the pure literal rule, and thegreedy algorithm for matchings in random graphs. In addition, these tools allow generalizations of these problems not previously analyzed to be analyzed in a straightforward manner. We illustrate our methodology on the three problems listed above


Published in:
Proceedings of the 30th annual ACM Symposium on Theory of Computing, STOC 1998, 249-258
Year:
1998
Publisher:
ACM Press
Keywords:
Laboratories:




 Record created 2007-01-26, last modified 2018-07-07


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)