Invited Speakers
Valerie King | University of Victoria
Title: The dynamic connectivity problem
Abstract: The problem of maintaining a spanning forest in a changing graph has been studied for over 40 years. It continues to give rise to interesting ideas with applications in a variety of settings, including communication complexity and random graphs. Still, some fundamental gaps in our understanding remain. We’ll look at some approaches to the problem, in the sequential, parallel, and distributed models, and their broader implications.
Short Bio (click to expand)
Valerie King is Professor in the Computer Science department at the University of Victoria Canada. She is an ACM Fellow, cited for her work on randomized algorithms, especially dynamic graph algorithms and fault-tolerant distributed computing. She currently serves on the SIGACT Executive Board, the editorial board of the new online journal TheoretiCS, and prize committees for the EATCS and ACM. She is general co-chair of ICDCN 2024, and co-organizer of a PIMS series on the mathematics of ethical decision-making systems. Dr. King received her PhD in computer science in 1988 from UC Berkeley, under the supervision of Richard Karp; JD from the UC Berkeley School of Law in 1983; and AB from Princeton University in mathematics. She has held visiting professor positions at the Technion, Hebrew University, University of Copenhagen, and Ecole Normale Supérieure in Paris and industrial research positions at Microsoft Research (Silicon Valley), HP and Compaq Systems Research Lab, and NECI in Princeton. She has been a member of the Institute for Advanced Study in Princeton, and a long-term visitor to the Simons Institute. She serves regularly as co-organizer of workshops and conferences and as a member of technical committees and panels, including the Independent Panel on Internet Voting for Elections BC, and as program committee chair of STOC 2017. She is the author of over 85 refereed publications.Joseph S.B. Mitchell | Stony Brook University
Title: Approximation Algorithms for Some Geometric Packing and Covering Problems
Abstract: A fundamental class of combinatorial optimization problems involve packing and covering. Examples include maximum independent set, dominating set, set cover, hitting set, etc. Motivated by applications in sensor networks and robotics, natural instances of such problems arise in geometric situations, such as covering points with a small number of disks, viewing “art galleries” with a small number of guards or with a mobile guard on a short route, packing disks or other shapes within a bounded domain, etc. Almost all of these problems are NP-hard even in simple two-dimensional settings. The problems get even harder when we take into account uncertain data, time constraints for scheduled coverage, and routing/connectivity problems in combination with coverage constraints. We discuss several of these geometric optimization problems from the perspective of approximation algorithms and we describe some techniques that have led to new or improved bounds or running times for selected packing, covering, and routing/coverage problems.
Short Bio (click to expand)
Joe Mitchell is Distinguished Professor of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University. He currently serves as Chair of the AMS Department. He holds BS/MS degrees from Carnegie Mellon University and a PhD from Stanford (advised by Christos Papadimitriou). Prior to joining Stony Brook, Joe was on the faculty of Cornell University. Joe has received various research recognitions (ACM Fellow, 2010 Goedel Prize, NSF Presidential Young Investigator, Fulbright Scholar, President's Award for Excellence in Scholarship and Creative Activities) and numerous teaching awards. His research is broadly in the area of algorithms, particularly in computational geometry. His interests include optimization problems, approximation algorithms, geometric networks, and applications of algorithms to problems in robotics, transportation, autonomous vehicle routing, sensor networks, computer graphics, manufacturing, geographic information systems, and computer vision.Tselil Schramm | Stanford University
Title: Studying information-computation gaps via “reductions between algorithms”
Abstract: In many high-dimensional statistics problems, we observe information-computation tradeoffs: given access to more data, statistical estimation and inference tasks require fewer computational resources. Though this phenomenon is ubiquitous, we lack rigorous evidence that it is inherent. In the current day, to prove that a statistical estimation task is computationally intractable, researchers must prove lower bounds against each type of algorithm, one by one, resulting in a “proliferation of lower bounds”. In this talk, I will discuss a different strategy: giving “reductions between algorithms” by proving that the performance of different algorithms is equivalent for a large universality class of statistical problems. I will broadly survey some recent results, and then focus on a “reduction” between statistical query algorithms and low-degree polynomials for hypothesis testing.
Short Bio (click to expand)
Tselil Schramm is an assistant professor of Statistics at Stanford University. Before joining Stanford, she received her PhD from U.C. Berkeley and was also a postdoc at Harvard and MIT. She is broadly interested in the theory of algorithms, optimization, and computational complexity, especially for problems arising in statistics. Her work aims to develop algorithmic tools for high-dimensional estimation problems and to characterize and explain information-computation tradeoffs.Diane Souvaine | Tufts University
Title: Reconfiguration Algorithms
Abstract: This talk focuses broadly on the topic of reconfiguration. The first part reviews various tools and techniques developed over the years for creating geometric reconfiguration algorithms. The second part focuses on recent algorithmic results in geometric reconfiguration motivated by challenges in electing a representative government. The final part shifts gears to address reconfiguration that has occurred in the computational geometry community over 35 years, ongoing advances, and the national/international need for additional reconfiguration that needs to drive a search yet again for new algorithms.
Short Bio (click to expand)
Dr. Diane Souvaine’s research contributions range from solving challenging problems in theoretical computational geometry to practical application across disciplines. She was elected a Fellow of the Association for Computing Machinery (2011), of the American Association for the Advancement of Science (2016), and of the Association for Women in Mathematics (2020) and has been a Fellow of the Radcliffe Institute for Advanced Study and a Member of the School of Mathematics at the Institute for Advanced Study. Dr. Souvaine served on the National Science Board from 2008-2020 (NSB Chair, 2018-2020; NSB Vice Chair, 2016-2018). A Professor of Computer Science and Mathematics at Tufts University since 1999, she has held the following leadership roles: Senior Advisor to the Provost, 2016-2018; Vice Provost for Research, 2012-2016; Chair of the Computer Science Department, 2002-2009. Previously at Rutgers University, she served 2.5 years in the Directorate of the NSF Science and Technology Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). She currently serves on the Board of Trustees and the Executive Committee for the Computer History Museum and on the Board of Trustees and the Finance Committee of TERC.Ileana Streinu | Smith College
Title: Geometry and Matter
Abstract: Techniques and ideas from discrete and computational geometry, rigidity theory, matroids, graph theory and computational algebra can be brought together to shed new light on geometric problems inspired by crystallography and materials science. Here, the objects of study are molecules and crystals modeled as mechanical frameworks: geometric graphs (finite or periodic) subject to distance constraints. I will focus on a small selection of my favorite problems, from reconstruction of molecular structures (“coordinates from distances”) to the design of flexible structures with “unusual” mechanical behavior.