Invited Speakers

Valerie King | University of Victoria

Title: The dynamic connectivity problem

Valerie King 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

Joseph S.B. Mitchell 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”

Tselil Schramm 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

Diane Souvaine 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

Ileana Streinu 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.

Short Bio (click to expand) Ileana Streinu earned a PhD in computer science from Rutgers, the State University of New Jersey and a doctorate in mathematics/theoretical computer science from the University of Bucharest, in Romania, both in 1994. She is is the Charles N. Clark professor of Computer Science and Mathematics at Smith College in Massachusetts and is also affiliated as an adjunct professor in the Manning College of Information & Computer Sciences of the University of Massachusetts Amherst. Her research addresses geometric problems emerging in a variety of applied areas of science, from mechanics, robotics, computer-aided design, statistics or sensor networks to crystallography and molecular modeling. Underlying all these problems are geometrically constrained structures called linkages or mechanical frameworks. Their rigidity and flexibility properties are translated in combinatorial terms to enable the study of their possible deformations and motion from the point of view of classical kinematics. This line of work draws upon techniques and ideas from discrete and computational geometry, rigidity theory, matroids and graph theory and extends into interdisciplinary directions, ranging from origami and robotics to bio-geometry. It also has applications in computational biology and computational materials science, and the web application KINARI developed in Prof. Streinu's group facilitates the investigation of rigidity and flexibility properties of proteins and other macro-molecules. Streinu was elected as a fellow of the American Mathematical Society as part of the 2013 inaugural class. She has received the 2010 David P. Robbins Prize of the American Mathematical Society for her algorithmic solution to the “carpenter’s rule problem" in linkage theory. Together with Ciprian Borcea, she was awarded the 2004 Grigore C. Moisil Award of the Romanian Academy for their paper on the number of embeddings of minimally rigid graphs.