Show simple item record

dc.contributor.authorSrinivasan, Aravinden_US
dc.date.accessioned2007-04-23T16:31:57Z
dc.date.available2007-04-23T16:31:57Z
dc.date.issued1993-08en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1378en_US
dc.identifier.urihttps://hdl.handle.net/1813/6152
dc.description.abstractRandomness is well-recognized as an important computational resource in theoretical computer science. Not only are there classical problems for which the only known "efficient" solutions are randomized, but there are problems for which randomness can be used to circumvent deterministic lower bounds. However, standard tools available for probabilistic analysis such as the Chernoff-Hoeffding bounds are not sufficiently powerful in all situations; second, since there are no known "true" sources of randomness, there is a need to develop general techniques for reducing/removing randomness from randomized algorithms. This thesis addresses these two issues. Certain types of scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. In Chapter 2, we present a fast and simple randomized algorithm for edge coloring a graph, in the synchronous distributed point-to-point model of computation. Our algorithm computes an edge-coloring of a graph $G$ with $n$ nodes and maximum degree $\Delta$ with at most $(1.6 + \epsilon) \Delta + O(\log^{2+\delta} n)$ colors with high probability, for any fixed $\epsilon, \delta, greater than 0$. To analyze our algorithm, we introduce techniques for proving upper bounds on the tails of random variables, extending the Chernoff-Hoeffding (CH) bounds to some types of dependent random variables. This is joint work with A. Panconesi [91]. In Chapter 3, we show that the CH bounds for the tails of the sums of bounded and independent random variables $X_{1}, \ldots, X_{n}$ require only limited independence among the $X_{i}$s. We show that if $X_{1}, \ldots, X_{n}$ lie in [0,1] and are $k$-wise independent, then $Pr(X \geq E[\sum_{i}X_{i}](1 + \delta))$ can be upper bounded by the CH bound, if $k \geq \mu \cdot min\{\delta,\delta^{2}\}$. This leads to algorithms that require a reduced amount of randomness for any analysis which uses the CH bounds. This is joint work with J.P. Schmidt and A. Siegel [108]. In Chapter 4, we present an $RNC^{2}$ algorithm for the perfect matching problem which uses $O(\log Z)$ random bits where $Z$ is any given upper bound on the number of perfect matchings in the graph, generalizing results of Grigoriev and Karpinski. Underlying our algorithm is a randomness-optimal generalization of the Isolating Lemma of Mulmuley, Vazirani and Vazirani, which also leads to other applications. This is joint work with S. Chari and P. Rohatgi [26].en_US
dc.format.extent9440563 bytes
dc.format.extent2011835 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleTechniques for Probabilistic Analysis and Randomness-Efficient Computationen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics