We are very excited to welcome the following keynote speakers
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.
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).
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
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.
The preliminary conference program will be published below.