Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms

ABSTRACT
We present recent results of the author and his colleagues on three problems related to the probabilistic analysis of algorithms:

Multiway Partitioning of a Graph
In this problem a graph G with n vertices is given, and we wish to partition the vertex set into k sets of size n/k so as to minimize the number of edges whose end points lie in different sets. We study this problem in a ``planted partition'' model, in which a good partition is planted in the graph but not revealed to the algorithm. This is joint work with Anne Condon.

The Threshold for k-Orientability
A graph is called k-orientable if its edges can be oriented so that no more than k edges are oriented towards any vertex. We present a general conjecture as to the threshold for k-orientability in random graphs, and describe the current status of the proof. This is joint work with Michael Saks. The problem was suggested by Juan Alemany and Jayram Thathachar in connection with a problem of assigning files to disks to ensure efficient access to many files in parallel.

Proofs of Unsatisfiability for Random 3-CNF Formulas
We present reasonably tight bounds on the length of the shortest resolution proof of unsatisfiability for a random unsatisfiable 3-CNF formula with n variables and m clauses. We concentrate on an upper bound based on an analysis using random graphs of a well-known algorithm for testing the satisfiability of a 2-CNF formula. The more challenging lower bound is due to my coauthors, Paul Beame, Toniann Pitassi and Michael Saks. In the course of deriving these results we illustrate a number of techniques, including the use of differential equations, for analyzing random walks and other stochastic processes.