New Frontiers in Structure vs Randomness with Applications to Combinatorics, Complexity, and Algorithms

Explore new frontiers in the structure vs. randomness paradigm and its applications to combinatorics, complexity, and algorithms in this illuminating conference talk. Delve into the Erdos-Turan problem concerning equally spaced numbers in large sets, tracing its evolution from 1936 to recent exponential improvements. Examine the speaker's innovative variant of the structure vs. randomness paradigm and its impact on three key areas: the Erdos-Turan problem, communication complexity with explicit separations between randomized and deterministic multi-party protocols, and algorithm design, focusing on fast combinatorial algorithms for triangle detection in graphs. Gain insights into cutting-edge research that bridges theoretical foundations and practical applications in computer science and mathematics.