Travel: Frontiers in Complexity Theory: A Graduate Workshop

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University plans to hold “Frontiers in Complexity Theory: A Graduate Student Workshop” at Rutgers University on July 29–August 1, 2024. The workshop will bring together a large cohort of graduate students working in theoretical computer science to learn about some of the most recent trends in complexity research. The event will be the concluding event of the DIMACS Special Focus on Lower Bounds in Computational Complexity, which is itself part of the DIMACS/Simons Institute Collaboration on Lower Bounds in Computational Complexity. The workshop is structured around four “mini-workshops,” each consisting of a series of three two-hour tutorial-style lectures that guide participants from foundational ideas to recent breakthroughs in a current area of complexity theory research. The mini-workshops are: 1) Meta-complexity, 2) Error-correcting Codes, 3) Algebraic Complexity, and 4) Derandomization. Each participant will attend two of the four mini-workshops, attend keynote presentations by the preeminent researchers Avi Wigderson and Ryan Williams, and hear an extended presentation on a recent breakthrough result showing the existence of locally testable codes that have both constant relative distance and rate and are testable with a constant number of queries. By gathering a large cohort of 70-80 graduate students from across the United States and placing them at the forefront of current research in complexity theory, the workshop has the potential to be formative for the relevant generation of complexity theorists, with lasting effects on the field. This award provides accommodations that makes it possible to host these students for the duration of the workshop. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.