Publication Details
Title: Analysis of Random Processes via And-Or Tree Evaluation
Author: M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi
Group: ICSI Technical Reports
Date: November 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-042.pdf
Overview:
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. including random loss-resilient codes, solving random k-SAT formulae using the pure literal rule, the greedy 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.
Bibliographic Information:
ICSI Technical Report TR-97-042
Bibliographic Reference:
M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi. Analysis of Random Processes via And-Or Tree Evaluation. ICSI Technical Report TR-97-042, November 1997
Author: M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi
Group: ICSI Technical Reports
Date: November 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-042.pdf
Overview:
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. including random loss-resilient codes, solving random k-SAT formulae using the pure literal rule, the greedy 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.
Bibliographic Information:
ICSI Technical Report TR-97-042
Bibliographic Reference:
M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi. Analysis of Random Processes via And-Or Tree Evaluation. ICSI Technical Report TR-97-042, November 1997