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].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.[A1] Chi-Jen Lu,
[A2] Tom Leighton, Chi-Jen Lu, Satish Rao, and Aravind Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, to appear in SIAM Journal on Computing.
[A3] Chi-Jen Lu, Deterministic hypergraph coloring and its applications, in Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 35--46, 1998.
[A4] Chi-Jen Lu and Shi-Chun Tsai, A note on iterating an a-ary Gray code, SIAM Journal on Discrete Mathematics, 14 (2), pp. 237--239, 2001.