Keynotes
We are very excited to welcome the following keynote speakers
Tim Roughgarden
Data-Driven Algorithm Design
Abstract
The best algorithm for a computational problem generally depends on the “relevant inputs”, a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem.
We adapt concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models are straightforward to understand, but also expressive enough to capture several existing approaches in the theoretical computer science and AI communities, ranging from self-improving algorithms to empirical performance models. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.
Joint work with Rishi Gupta.
Biography
Tim Roughgarden is a Professor of Computer Science and member of the Data Science Institute at Columbia University. Prior to joining Columbia, he spent 15 years on the computer science faculty at Stanford, 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. He has written or edited ten books and monographs, including Twenty Lectures on Algorithmic Game Theory (2016), Beyond the Worst-Case Analysis of Algorithms (2020), and the Algorithms Illuminated book series (2017-2020).
Adi Livnat
Sex, recombination and the fundamental nature of mutation
Abstract
The role of sexual recombination in evolution has been called "the queen of problems" in evolutionary biology. Although multiple hypotheses for it have been proposed during the 20th century, none has been able to account for the prevalence of sex in nature. At the same time, a sea of change is underway regarding our empirical knowledge on the nature of genetic change in biological evolution.
In this talk, I will discuss a new way of thinking about the role of sexual recombination in biological evolution and how it made an interdisciplinary contribution by motivating the development in computer science of a key breakthrough that, together with other breakthroughs, enabled the deep learning revolution. In addition, I will discuss new evidence from my lab on the fundamental nature of mutation and how mutation and recombination may be connected. Sexual recombination and mutation are two of the three most basic elements of evolution, the third being selection. Thus, the implications of a new understanding of them reach beyond biological evolution and could inform new developments in evolutionary computation as well, in addition to holding promise for contributing to the understanding of genetic disease and cancer.
Joint work (in several papers) with Christos Papadimitriou, Nick Pippenger, Marc Feldman, Jonathan Dushoff, Umesh Vazirani, Erick Chastain and Liudmyla Vasylenko
Biography
Adi Livnat received his undergraduate degree in Biology from Stanford University, his Ph.D. in Ecology and Evolutionary Biology from Princeton University, and was a Miller Fellow at the Miller Institute for Basic Research in Science at UC Berkeley in the Computer Science Division. He is currently a Associate Professor at the Department of Evolutionary and Environmental Biology and the Institute of Evolution at the University of Haifa in Israel. He studies fundamental questions regarding the process of evolution and how it leads to the complexity of life. He has proposed a new way of looking at the biological evolutionary process – interaction-based evolution – based on a re-examination of biological recombinational and mutational mechanisms. His lab employs a wide range of techniques to study mutation and recombination, from mathematical models to cutting-edge experimental methods, while at the same time working to expand the bridge between evolutionary biology and theoretical computer science and to examine the evolutionary process through the computational lens. Questions of interest include the role of sexual recombination in evolution, the fundamental nature of mutation and the potential connection between these two century-old problems.
Accepted papers
We look forward to the following authors presenting their excellent work at FOGA 2021:
- Laurent Meunier, Iskander Legheraba, Yann Chevaleyre and Olivier Teytaud. Asymptotic convergence rates for averaging strategies
- Carsten Witt. On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution Algorithms*
- Luke Branson and Andrew Sutton. Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems*
- Dogan Corus, Pietro S. Oliveto and Donya Yazdani. Automatic Adaptation of Hypermutation Rates for Multimodal Optimisation
- Mario Alejandro Hevia Fajardo and Dirk Sudholt. Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff Function*
- Nils Müller and Tobias Glasmachers. Non-Local Optimization: Imposing Structure on Optimization Problems by Relaxation
- Jonathan Heins, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann and Pascal Kerschke. On the Potential of Normalized TSP Features for Automated Algorithm Selection*
- Jakob Bossek and Dirk Sudholt. Do Additional Optima Speed Up Evolutionary Algorithms?
- Adel Nikfarjam, Jakob Bossek, Aneta Neumann and Frank Neumann. Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation
- Denis Antipov and Naumov Semen. The Effect of Non-symmetric Fitness:The Analysis of Crossover-Based Algorithms on RealJump Functions
The * markers indicate the nomination for the FOGA2021 best paper award. The winner will be determined by online voting during the conference.
Click here to acess the FOGA2021 Proceedings in the ACM Digital Library
Program
The conference program is now available below.
As a virtual event FOGA2021 is realized using the MS teams platform. The following document provides some useful information on the conference implementation. Brief Guideline to Virtual Conference Implementation
In case of questions, don't hesitate to contact the organizers.
| Time (UTC+2h) | Topic / Title | Speaker |
|---|---|---|
| 12:00 - 12:30 | Opening | Organizers |
| 12:30 - 13:30 | Non-Local Optimization: Imposing Structure on Optimization Problems by Relaxation | Nils Müller and Tobias Glasmachers |
| 14:00 - 15:30 | Keynote: Sex, recombination and the fundamental nature of mutation | Adi Livnat |
| 16:00 - 17:00 | Asymptotic Convergence Rates for Averaging Strategies | Laurent Meunier, Iskander Legheraba, Yann Chevaleyre and Olivier Teytaud |
| 17:30 - 18:30 | Do Additional Optima Speed Up Evolutionary Algorithms? | Jakob Bossek and Dirk Sudholt |
| Time (UTC+2h) | Topic / Title | Speaker |
|---|---|---|
| 10:00 - 11:00 | Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation | Adel Nikfarjam, Jakob Bossek, Aneta Neumann and Frank Neumann |
| 11:30 - 12:30 | The Effect of Non-symmetric Fitness:The Analysis of Crossover-Based Algorithms on RealJump Functions | Denis Antipov and Naumov Semen |
| 15:00 - 16:00 | On the Potential of Normalized TSP Features for Automated Algorithm Selection | Jonathan Heins, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann and Pascal Kerschke |
| 16:30 - 17:30 | Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problem | Luke Branson and Andrew Sutton |
| Time (UTC+2h) | Topic / Title | Speaker |
|---|---|---|
| 10:00 - 11:00 | On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution Algorithms | Carsten Witt |
| 11:30 - 12:30 | Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff Function | Mario Alejandro Hevia Fajardo and Dirk Sudholt |
| 15:00 - 16:00 | Automatic Adaptation of Hypermutation Rates for Multimodal Optimisation | Dogan Corus, Pietro S. Oliveto and Donya Yazdani |
| 16:30 - 18:00 | Keynote: Data-Driven Algorithm Design | Tim Roughgarden |
| 18:00 - 18:30 | Closing | Organizers |