Three Topics in Combinatorics with Relations to Theoretical Computer Science

Yale University, New Haven CT

Investigators

Abstract

We intend to study three topics in combinatorics which are related to theoretical computer science. We will study the diameter problem for graphs of polytopes aiming at a polynomial upper bound, and also try to find versions of the simplex algorithm with sub-exponential worst case behavior. We will study Boolean functions, their Fourier transform and how it relates to questions in probability and complexity. We will also try to find general methods to relate the solution of a positive integer programming problem and its linear programming relaxation. Combinatorics have now become the central mathematical discipline in theoretical computer science (and various applied areas of computer science as well). The role of combinatorics in computer science today is quite similar to the role of logic in the early days of computation. Problems from theoretical computer science enriched and enforced combinatorial thinking and areas which were regarded as having clear intellectual merit have gained surprising real-life applications. Linear programming and the simplex algorithm are among the most important applications of computers and in our earlier work as well as the planned research. We intend to study fundamental questions concerning linear programming. Another area of our research, the Fourier analysis of Boolean functions is a relatively new area which we helped to develop in the past. In view of the importance of Fourier analysis in other areas we should not have been surprised to see its recent applications in combinatorics and complexity theory and we intend to explore further connections.