Parallel Algorithm Engineering Reconsidered
Peter Sanders (Karlsruhe Insitute of Technology)
Abstract
Algorithm engineering is a view on the methodology of algorithmic research. At its core is a feedback cycle of modeling, design, analysis, implementation, and experimental evaluation [Bader, Moret, Sanders, Experimental Algorithmics, 2002; Sanders, Efficient Algorithms, 2009]. At each stage, we learn new things about an algorithmic problem that drives the development of better solutions. This is inspired by the hypothesis-driven cycle of scientific discovery prevalent in the natural sciences [Popper, Logik der Forschung, 1934].
The invited talk reflects on the role of algorithm engineering with particular focus on parallel computing. Modeling is particularly important there because no standard model has emerged after more than half a century of research on parallel algorithms. For example, MapReduce computations have become a popular high-level theoretical model but their connection to the real world is an interesting question [Sanders, IEEE Conf on Big Data, 2020]. On the low-level end of this spectrum, we need models that enable extensive algorithm-hardware codesign needed for future energy-efficient AI hardware.
On the design side, it emerges that we do not just need a single algorithm but rather a spectrum of solutions selected from a huge design space of possible algorithms. This spectrum can then cover a range of inputs and machines. To grasp this on the analysis side, we need to take constant factors into account and handle complex models. Implementation has moved from a simple transition stage to extensive performance engineering to take various kinds of parallelism into account, e.g., bits, SIMD, instructions, threads in hierarchies of caches, and multipe compute nodes. This can result in orders of magnitude performance differences, often outstripping asymptotic behavior.
Experiments and the entire cycle are now in a revolutionary stage where AI assisted algorithm engineering can drive the cycle at unprecedented speed. As human researchers, we rapidly have to learn how to control it.
Biography
Peter Sanders received his PhD in Computer Science from Universität Karlsruhe in 1996. After a short postdoctoral period at Chalmers University in Gothenburg, Sweden, he joined the Max Planck Institute for Informatics in Saarbrücken. In 2004, he returned to Karlsruhe as a full professor. He currently leads the Algorithm Engineering Group in the Institute for Theoretical Computer Science at the Karlsruhe Institute of Technology (KIT). He also works part-time for Google.
Professor Sanders has received numerous honors and awards, including the DFG Leibniz Award in 2012 and a 2020 ERC Advanced Grant for the project “Engineering Scalable Algorithms for the Basic Toolbox (ScAlBox)”. He has authored more than 300 publications, primarily in the area of algorithms for large-scale data processing.
His research spans a broad range of topics, including parallel algorithms (such as sorting, SAT solving, data structures, multicore algorithm libraries, load balancing, and communication scheduling), memory hierarchies (caches, disks, and storage servers), graph algorithms (including route planning and graph partitioning), randomized algorithms, compressed data structures, and full-text indexing.
Highly Asynchronous Concurrency in Data Structures
Robert Tarjan (Princeton University)
Abstract
This talk will explore whether and by how much operations on data structures can be sped up by using multiple highly unsynchronized threads. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and the speaker on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization. It will also discuss ongoing work with Laxman Dhulipala, Jakub Łącki, and Siddhartha Jayanti on finding maximal matchings, as well as the general question of what we should require in a realistic but theoretically tractable model of highly asynchronous concurrency.
Biography
Robert E. Tarjan, the James S. McDonnell Distinguished University Professor of Computer Science, joined Princeton in 1985. He received doctoral and master’s degrees in computer science from Stanford in 1972 and 1971, respectively, after earning a bachelor’s in mathematics from Caltech. His academic experience involved assistant professorships at Cornell and Stanford, and a Miller research fellowship at UC, Berkeley. Professor Tarjan’s extensive involvement in the private sector includes past and continuing fellowship, research and scientific roles at the NEC Research Institute, Princeton; InterTrust Technologies, Sunnyvale, CA; Compaq Computer, Houston, TX; Hewlett-Packard, Palo Alto, CA; and Microsoft, Mountain View, CA.
Professor Tarjan was awarded the ACM Turing Award in 1986 for fundamental achievements in the design and analysis of algorithms and data structures. He was the first winner of the Rolf Nevanlinna Prize (now called the Abacus Prize), established in 1982 and awarded every four years for outstanding contributions in mathematical aspects of information sciences by the International Mathematical Union. His other honors include Caltech’s Distinguished Alumni Award in 2010, the 2009 Edelman Award from INFORMS (member of winning H-P team), fellow of the Society for Industrial and Applied Mathematics (2009), and the Blaise Pascal Medal in Mathematics and Computer Science from the European Academy of Sciences in 2004.
The Omega(D+sqrt(n)) Lower Bound Story of Distributed Algorithms
Gopal Pandurangan (University of Houston)
Abstract
This talk will trace the interesting (hi)story behind the 2026 Dijkstra Prize work, “Distributed Verification and Hardness of Distributed Approximation” [STOC 2011, SICOMP 2012], by Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, and Wattenhofer. The talk will trace the origin of the $\tilde{\Omega}(D+\sqrt{n})$ lower bound, first shown for the fundamental distributed Minimum Spanning Tree (MST) problem, to the discovery that the same bound applies to a wide variety of problems and settings known today. Along the way, it will talk about the impact of this work on distributed algorithms research over the last 15 years.
Biography
Gopal Pandurangan is a Moores Professor in the Department of Computer Science at the University of Houston, USA. He received his Ph.D. in computer science from Brown University in 2002. He has held faculty positions at Purdue University and Nanyang Technological University, Singapore, as well as visiting positions at the Indian Institute of Technology at Madras, Brown University, and Rutgers University. His research interests are in the theory and algorithms for distributed computing, networks, quantum computing, machine learning, and big data, and he has published over 150 refereed papers. He is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), a recipient of the University of Houston Research Excellence Award, and a winner of the ACM PODC 2025 Best Paper Award.