Next: Richard J. Cole Up: Faculty Previous: Marsha J. Berger

Ravi B. Boppana

Associate Professor of Computer Science
Ph.D., Massachusetts Institute of Technology

Professor Boppana works in theoretical computer science. Most of his work has been in two areas: lower bounds and probabilistic methods. The first area, lower bounds, involves showing that algorithms for specific problems must consume a lot of resources. He has developed lower bounds in various computational models, including Boolean circuits, parallel machines, and decision trees. The second area, probabilistic methods, involves the development of tools from probability theory and applying them to computer science problems. He has applied probabilistic methods to various domains, including distributed algorithms, pseudo-randomness, and logic. Currently, he is working on the competitive analysis of randomized algorithms (e.g., on-line algorithms for the server problem). Finally, he is planning to write a book on ``Mathematical Methods in Computer Science''.

  1. R. Boppana and B. Narayanan, (1995). ``The biased coin problem,'' to appear in SIAM Journal on Discrete Mathematics. Preliminary version in Proceedings of the Symposium on Theory of Computing, 25:252--257, ACM Press.

  2. R. Boppana, (1994). ``The decision-tree complexity of element distinctness,'' Information Processing Letters, 52:329--331.

  3. R. Boppana and M. Sipser, (1990). ``The complexity of finite functions,'' Handbook of Theoretical Computer Science, A:759--804, Elsevier Science Publishers.