Applications of Artihmetic Combinatorics in Computer Science

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Recent progress in arithmetic combinatorics has benefited from a convergence of methods from analysis, ergodic theory, combinatorics, and graph theory. This new machinery has led to spectacular progress on long-standing open questions, such as the Green-Tao theorem on arbitrarily long arithmetic progressions in the primes. This research is a systematic exploration of applications of such new techniques to theoretical computer science. Some of the analytic, graph-theoretic and combinatorial techniques have already had a number of applications to theoretical computer science, in such diverse areas as the design of sub-linear time algorithms, the construction of randomness extractors and the design of probabilistically checkable proofs. This research explores new applications of such techniques, as well as applications of the ergodic-theoretic techniques. This research is primarily concerned with a ""technology transfer"" from arithmetic combinatorics to computer science: increased collaboration between pure mathematicians working in arithmetic combinatorics and theoretical computer scientists will, however, be beneficial to both fields, and is likely to have a positive impact beyond theoretical computer science.