Algorithms and Discrete Mathematics

1. Lovas Local Lemma, Randomized Rounding, and Applications:

The Lovasz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy-Reed) have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this, by providing algorithmic approaches to two families of applications of the LLL [A1, A2]. The first provides new algorithmic results on constructing disjoint paths in graphs; the second provides an improved approximation algorithm for a Minmax Integer Programming (MIP) problem. One common theme of our work is a ``gradual randomized rounding'' approach. The MIP problem models important problems such as hypergraph-coloring and low-congestion routing, and can be applied to support divide and conquer approaches [A3].

2. Period of Binomial Coefficients:

In [A4], we consider the number of distinct a-ary codes produced by repeatedly applying the Gray code mapping of Sharma and Khanna. This number was derived before by Lichtner, and we give a simpler proof. Our key observation is a simple connection between this number and the period of binomial coefficients modulo a. Then the result follows immediately from a known periodic property of binomial coefficients modulo a. Such periodic property turns out to have applications to complexity theory too.

3. Selected Results: