This proposal aims to transform research in mathematics and computer science by bringing together two major research tracks which have been progressing in parallel (albeit with nontrivial interaction). In mathematics, the object of study in many areas (including analysis, number theory, ergodic theory and combinatorics) is captured by the question: ?What random-like properties does a (deterministic) mathematical structure have?? In computer science, the object of study in many areas (including network theory, error correction, computational complexity and derandomization) is captured by the question ?Can we deterministically and efficiently design objects with specific random-like properties??
The PIs view the two Math and CS tracks (respectively) as analytic and synthetic approaches for understanding the same fundamental pseudorandomness phenomena and its interaction with structure.
Computer science has been mostly a passive consumer of mathematics, relying on the mathematical analysis of structures to build desireable objects. We propose to transform this one-way use to a full fledged collaboration, through the use of the computational view of randomness to analyze mathematical structures. Preliminary applications of this tool, many by the PIs, have already led to major breakthroughs both in new understanding of mathematical objects and in the use of these objects as the basis for constructions in computer science. Examples of recent breakthroughs resulting from this cross-fertilization include work on expanders in Cayley graphs, extractors from sum-product theorems, arithmetic (and other) progressions in primes, and the use of Gowers? norms in complexity. Many rely on the conceptual computational tool of pseudorandomness, the inability of any of a class of tests to tell the difference between a random object and the object in question. This notion arose in complexity-theoretic approaches to cryptography, but has since had wide applicability in computer science (e.g. in derandomizing probabilistic algorithms).
