ALGO 2018: Keynote speakers
ESA 2018
Claire Mathieu · CNRS, Paris
Stable Matching in Practice
Stable matching methods, based on the algorithm designed by Gale and Shapley, are used around the world in many applications such as college admissions. Several criteria measure the quality of the result: number of students assigned; rank of the college assigned to the applicant in their preference list; robustness; running time; etc.
After reviewing properties of the algorithm in the pure, ideal setting, we present issues arising in practice. The input data is uncertain and evolves with time, so a one-shot algorithm does not suffice. It is not feasible for admission committees to meet continuously, so the process cannot be fully dynamic. To reconcile those competing constraints, a hybrid implementation proceeding partly online on the student side was recently proposed for college admissions in France. The system also incorporates side constraints on joint assignment to schools and to dorms.
Claire Mathieu does research on the design and analysis of algorithms, with a focus on approximation algorithms, particularly approximation schemes for NP-hard problems. A former student of Ecole normale supérieure, she received a PhD in Computer Science in 1988 at Paris-Sud University. She has held research and faculty positions at CNRS, Paris-Sud University, Ecole Polytechnique, Brown University, and Collège de France. She is currently a CNRS research director in Paris, France.
Tim Roughgarden · Stanford
How Computer Science Informs Modern Auction Design
Over the last twenty years, computer science has relied on concepts borrowed from game theory and economics to reason about applications ranging from internet routing to real-time auctions for online advertising. More recently, ideas have increasingly flowed in the opposite direction, with concepts and techniques from computer science beginning to influence economic theory and practice.
In this lecture, Tim Roughgarden will illustrate this point with a detailed case study of the 2016–2017 Federal Communications Commission incentive auction for repurposing wireless spectrum. Computer science techniques, ranging from algorithms for NP-hard problems to nondeterministic communication complexity, have played a critical role both in the design of the reverse auction (with the government procuring existing licenses from television broadcasters) and in the analysis of the forward auction (when the procured licenses sell to the highest bidder).
Tim Roughgarden is a Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University. He joined the Stanford faculty in 2004, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society’s Tucker Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. His books include Twenty Lectures on Algorithmic Game Theory (2016) and Algorithms Illuminated (2017).
IPEC 2018
Stefan Kratsch and Magnus Wahlström, the recipients of the EATCS-IPEC Nerode Prize 2018, will give an invited talk at IPEC 2018.
Stefan Kratsch · Humboldt-Universität zu Berlin
Stefan Kratsch is a Professor for theoretical computer science at Humboldt-Universität zu Berlin. He did his PhD studies in 2008–2010 at Max-Planck-Institute for Informatics in Saarbrücken, and since then he has worked as a postdoc at Utrecht University and Max-Planck-Institute for Informatics, as a junior research group leader at Technical University Berlin, and Professor for theoretical computer science at University of Bonn. His research interests include parameterized complexity, efficient preprocessing, and computational complexity.
Magnus Wahlström · Royal Holloway, University of London
Magnus Wahlström is a Reader in computer science at Royal Holloway, University of London, where he has worked since 2013. He got his PhD in 2007 from the University of Linköping, Sweden, under the supervision of Peter Jonsson, and in between he worked at the Max-Planck-Institute for Informatics in Saarbrücken, Germany in the group of Kurt Mehlhorn. His research lies broadly in the fields of parameterized complexity, exact algorithms and CSPs.
WABI 2018
Mihai Pop · University of Maryland
From Clustering to Variant Discovery: Algorithmics Opportunities in Microbiome Research
Microbiology has undoubtedly been transformed by the emergence of metagenomics – the sequencing-based exploration of the genomic content of microbial communities. This field has made it possible to characterize the genomes and even functions of microbes that cannot currently be grown in a laboratory. As a result, new microbes and new microbial functions have been discovered in recent years.
In addition to this transformative effect on biology, the analysis of metagenomic data has created new opportunities for computational research. In my talk I will concentrate on algorithmic challenges related to sequence clustering, functional annotation, and structural variant discovery. I will describe recent results from my lab in these areas and also provide a broader outlook on unsolved challenges in this dynamic field.
Dr. Pop is a Professor in the Department of Computer Science and the Center for Bioinformatics and Computational Biology at the University of Maryland, College Park (UMCP) and currently serves as the Interim Director of the University of Maryland Institute for Advanced Computer Studies, and as the Director of the Center for Health-related Informatics and Bioimaging. Dr. Pop received his Ph.D. in Computer Science at Johns Hopkins University where he focused on algorithms for computer graphics and Geographic Information Systems (GIS) applications. Dr. Pop's current research interests include metagenomic assembly and analysis algorithms, software testing in bioinformatics, and dynamic models of microbial communities. His lab has developed a number of widely used open-source software tools, such as the assembly suite AMOS, the NGS aligner Bowtie, and the metagenomic assembly package MetAMOS. He also co-led the data analysis working group for the Human Microbiome Project and led the sub-group responsible for the assembly of the data generated in this project. Dr. Pop is actively involved in teaching at the undergraduate and graduate levels and is strongly interested in the development of educational resources for introductory computer science and bioinformatics.
WAOA 2018
Gerhard Woeginger · RWTH Aachen
Some Easy and Some Not So Easy Geometric Optimization Problems
The talk surveys several complexity and approximability results for geometric optimization problems that are built around norms with polyhedral unit balls.
Gerhard Woeginger is a professor at RWTH Aachen where he chairs the algorithms and complexity group. His research interests lie in the intersection area of Foundations of Computer Science, Discrete Mathematics and Operations Research. Concrete topics are approximation, scheduling, competitive analysis of online algorithms, parameterized complexity, graph theory; recently also algorithmic game theory and computational social choice.
Woeginger served as program chair of ESA 1997, ICALP 2003, the European Conference on Operational Research (EURO 2009), and of several other conferences. He received a Humboldt Research Award in 2011, and he was elected to the Academia Europaea in 2014.
Other invited speakers
In addition to the ALGO-wide keynote talks, ALGO conferences and workshops feature the following invited talks:
- ALGOCLOUD invited speaker: Roger Wattenhofer
- ALGOSENSORS invited speaker: Stefan Schmid
- ATMOS invited speaker: Dennis Huisman
- ESA test-of-time award: James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook
- IPEC invited tutorial: Radu Curticapean