Explorations in Algorithms

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The study of algorithms has yielded numerous techniques that are both interesting mathematically and broadly useful. This ranges from linear programming to cryptography to geometry to approaches for approximately solving optimization problems. The addition of a statistical view of the world to the study of algorithms has also been a compelling area of study. This project will study better algorithms for linear programming as well as, explore and expand on recent work in approximation algorithms, and will explore algorithms with a statistical view of the world. Recent breakthrough work on solving linear systems as well as developments in online optimization, make the development of better algorithms for linear programming a tantalizing possibility. This project will pursue this goal. A second specific area is the study of approximation algorithms which has, in recent years, been a primary focus of algorithms research. In particular, problems such as finding sparse cuts, disjoint paths, and the traveling salesman problem have been fertile ground for developing new algorithmic techniques. The researcher has done some of this work, and proposes to study this area further. Finally, this project will go beyond the ``we know how to solve it'' case of linear programming, and the ``we will do as well as we can'' notion of approximation algorithms, to a ``how do we do on data generated by the world'' view of algorithms. This latter view is especially appropriate these days with the growing production of biological data; This data is generated accordingly to scientifically validated statistical models. Quite interesting work has been done in this area, but the field is begging for more involvement from those trained in algorithms. The intellectual merit of this project lies in the further development of mathematical techniques for algorithms, and the blending of traditional ideas with ideas in statistics. The broader impacts lie in the many applications of algorithms for the problems addressed in this project. Application areas include network design, molecular biology, recommendation systems, and optimization. The researcher will introduce ideas from this project into graduate and undergraduate classes in algorithms as well.