Next: Ernest S. Davis Up: Faculty Previous: Ravi B. Boppana

Richard J. Cole

Professor of Computer Science
Ph.D., Cornell University

Professor Cole is interested in the design and analysis of algorithms. Recent work has been concentrated in the following areas: the design of efficient algorithms for the PRAM model of parallel computation, string and pattern matching algorithms, amortization as an analysis technique, and network emulation problems. A common thread is a continuing effort to improve and develop solutions for basic problems. For example, his string matching work includes the first relatively simple worst case analysis of the Boyer-Moore string matching algorithm. His current research interests include the following problems: how to cope with faults on networks of computing nodes, such as a mesh or a butterfly; how to quickly find good approximate matches among pairs or collections of patterns, motivated in part by biological problems; using approximate solutions as a bootstrapping technique in parallel algorithms for network problems and elsewhere.

  1. R. Cole, (1988). ``Parallel merge sort,'' in Proc. Twenty Seventh Annual Symposium on the Foundations of Computer Science, 1986, 511--516. SIAM Journal on Computing, 17:770--785.

  2. R. Cole, (1994). ``Tight bounds on the complexity of the Boyer-Moore string matching algorithm,'' in Proc. Second Annual ACM Symposium on Discrete Algorithms, 1991, 224--233. SIAM Journal on Computing, 5:1075--1091.

  3. R. Cole,, B. Maggs and R. Sitaraman, (1993). ``Multi-Scale Emulation: A technique for reconfiguring arrays with faults,'' in Proc. Twenty Fifth Annual ACM Symposium on the Theory of Computing, 561--570.