I shall explain an important result of my doctoral student Louis Mak: Every unit-cost random access machine (RAM) that runs in time T(n) can be simulated by a concurrent-read exclusive-write parallel random access machine (CREW PRAM) in time O(T^{1/2} log T). The proof is constructive; thus, it gives a mechanical way to translate any sequential algorithm designed to run on a unit-cost RAM into a parallel algorithm that runs on a CREW PRAM and obtain a nearly quadratic speedup. As a consequence, there is no recursive function that is inherently not parallelizable.

Cache coherence protocols coordinate access to shared memory in a multi-processor system. A central correctness requirement for such protocols is sequential consistency. A protocol is sequentially consistent if for each protocol run, the per-processor sequences of load and store operations in that run can be interleaved to obtain a serial trace. In a serial trace, each load returns the value of the most recent store to the same memory block. Modern sequentially consistent cache coherence protocols employ subtle optimizations for performance reasons, making it difficult to reason about their correctness. Thus, automated verification of such finite state protocols is highly desirable. Unfortunately however, the problem of determining whether a finite state protocol is sequentially consistent is undecidable. For practical purposes, the undecidability result can potentially be side-stepped if there is a class C of protocols with the following properties: membership in C is decidable, all members of C are sequentially consistent, and all protocols that arise in real sequentially consistent systems belong to C. In this talk, we propose a candidate for such a class. Roughly, protocols in our decidable class satisfy three constraints, which we believe to be true for real protocols. First, protocol transitions can be annotated to indicate if a memory block is copied, deleted, or untouched. Second, it can be determined in a finite state fashion from the annotated protocol run from which store operation each load inherits its value. Third, for any run, for each block, stores to that block can be reordered by a finite state machine to be consistent with the corresponding serial trace. A consequence of our decidability result that may be useful for practical, semi-automated verification is that membership in our class can be reduced to the language inclusion problem for regular languages, via manual construction of a finite state witness. This is joint work with Alan Hu, Marius Laza, and Rita Sharma.

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path and the total cost must not exceed a given budget. This problem generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, scheduling, and virtual-circuit routing. Kolliopoulos and Stein and later Dinitz, Garg, and Goemans developed algorithms improving the first approximation results of Kleinberg for the problem to minimize the violation of edge capacities and for other variants. However, none of the developed techniques is capable of providing solutions without relaxing the cost constraints. We give the first approximation results for hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem.

Bit commitment is a cryptographic protocol that allows one party (the committer) to give another party (the receiver) a sealed bit that the receiver does not know. The committed bit remains hidden until the committer reveals the value. The revealing process contains a proof that the value has not been modified. We introduce and construct timed-commitment schemes, an extension to the standard notion of commitments in which a potential forced opening phase permits the receiver to recover (with effort) the committed value without the help of the committer. As a result, the value of the bit is only guaranteed to remains hidden from the receiver for only a limited amount of time. An important application of our timed-commitment scheme is contract signing: two mutually suspicious parties wish to exchange signatures on a contract. We show a two-party protocol that allows them to exchange RSA or Rabin signatures. The protocol is strongly fair: if one party quits the protocol early, then the two parties must invest comparable amounts of time to retrieve the signatures. This statement holds even if one party has many more machines than the other. Other applications of timed commitments include honesty preserving auctions and collective coin-flipping. Joint work with Dan Boneh

A propositional proof system is called automatizable if there exists an algorithm which for any given tautology searches for its nearly optimal proof in this system within nearly optimal time. We show that neither Resolution nor tree-like Resolution is automatizable unless the hierarchy of parameterized problems by Donwey and Fellows collapses. This concrete new result will be preceded by a general discussion of automatizability and its relations to such important issues in Proof Complexity as Efficient Interpolation. Joint work with M. Alekhnovich.

Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to sequence the DNA in the missing gaps. This procedure has been used in a number of microbial sequencing projects including Streptococcus pneumoniae and other bacteria. In this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. In particular, given a collection of n/2 DNA fragments we describe a strategy that requires 0.75 n log n work in eight parallel rounds of experiments, closely matching a corresponding lower bound of 0.5 n log n. Joint work with Noga Alon, Mehmet Serkan Apaydin, Lance Fortnow, and Simon Kasif. Professor Beigel is supported in part by the National Science Foundation under grant numbers CCR-9996021 and CCR-0049019.