Now showing items 1-7 of 7

• Chernoff-Hoeffding Bounds for Applications with Limited Independence ﻿

(Cornell University, 1992-10)
Chernoff-Hoeffding bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables. We present a simple technique which gives slightly better bounds than these ...
• A Generalization of Brooks' Theorem ﻿

(Cornell University, 1992-09)
Given a connected graph $G = (V, E)$ with $n$ vertices and maximum degree $\Delta$ such that $\Delta \geq$ 3 and $G$ is not a complete graph, Brooks' theorem shows that $G$ is $\Delta$-colorable. We prove a generalization ...
• The Local Nature of $\Delta$-Coloring and Its Algorithmic Applications ﻿

(Cornell University, 1992-09)
Given a connected graph $G$ = ($V,E$) with $\mid$V$\mid$ = $n$ and maximum degree $\Delta$ such that $G$ is neither a complete graph nor an odd cycle, Brooks' theorem states that $G$ can be colored with $\Delta$ colors. ...
• On the Complexity of Distributed Network Decomposition ﻿

(Cornell University, 1993-06)
In this paper, we improve the bounds for computing a network decomposition, which is a basic notion in distributed graph algorithms, distributively and deterministically. Our algorithm computes an \$(n^{\epsilon(n)},(n ...
• Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds ﻿

(Cornell University, 1993-06)
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge coloring a graph, in the ...
• Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems ﻿

(Cornell University, 1993-06)
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuley, Vazirani and Vazirani[21] and in several ...
• Techniques for Probabilistic Analysis and Randomness-Efficient Computation ﻿

(Cornell University, 1993-08)
Randomness 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 ...