Three Topics in Combinatorics with Relations to Theoretical Computer Science

点击翻译按钮获取中文摘要

We intend to study three topics in combinatorics which are related totheoretical computer science. We will study the diameter problem forgraphs of polytopes aiming at a polynomial upper bound, and also try tofind versions of the simplex algorithm with sub-exponential worst casebehavior. We will study Boolean functions, their Fourier transform and howit relates to questions in probability and complexity. We will also try tofind general methods to relate the solution of a positive integerprogramming problem and its linear programming relaxation.Combinatorics have now become the central mathematical discipline intheoretical computer science (and various applied areas of computerscience as well). The role of combinatorics in computer science today isquite similar to the role of logic in the early days of computation.Problems from theoretical computer science enriched and enforcedcombinatorial thinking and areas which were regarded as having clear intellectual merit have gained surprising real-life applications. Linearprogramming and the simplex algorithm are among the most importantapplications of computers and in our earlier work as well as the plannedresearch. We intend to study fundamental questions concerning linearprogramming. Another area of our research, the Fourier analysis of Booleanfunctions 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 nothave been surprised to see its recent applications in combinatorics andcomplexity theory and we intend to explore further connections.