Invited Speakers
Constantinos Daskalakis
Title: Min-Max Optimization: From von Neumann to Deep Learning
Abstract: Deep Learning applications, such as Generative Adversarial Networks and other adversarial training frameworks, motivate min-maximization of nonconvex-nonconcave objectives. Unlike their convex-concave counterparts, however, for which a multitude of equilibrium computation methods are available, nonconvex-nonconcave objectives pose significant optimization challenges. Gradient-descent based methods commonly fail to identify equilibria, and even computing local approximate equilibria has remained daunting. We shed light on this challenge through a combination of complexity-theoretic, game-theoretic and topological techniques, presenting obstacles and opportunities for Deep Learning and Game Theory going forward.
(
This talk is based on joint works with Noah Golowich, Stratis Skoulakis and Manolis Zampetakis)
Bio: Constantinos (aka "Costis") Daskalakis is a Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long-standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi-item auctions. His current work focuses on high-dimensional statistics and learning from biased, dependent, or strategic data.
He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, and the Bodossaki Foundation Distinguished Young Scientists Award.
Daniel Marx
Title: Tight complexity results for algorithms using tree decompositions
Abstract: It is well known that hard algorithmic problems on graphs are easier to solve if we are given a low-width tree composition of the input graph. For many problems, if a tree decomposition of width k is available, algorithms with running time of the form f(k)*poly(n) are known; that is, the problem is fixed-parameter tractable (FPT) parameterized by the width of the given decomposition. But what is the best possible function f(k) in such an algorithm? In the past decade, a series of new upper and lower bounds gave us a tight understanding of this question for particular problems. The talk will give a survey of these results and some new developments.
Bio: Dániel Marx obtained his PhD in 2005 at the Budapest University of Technology and Economics in Hungary. After that, he had postdoc researcher and visiting researcher positions in Berlin, Budapest, and Tel Aviv. From 2012 to 2019, he was at the Institute for Computer Science and Control of the Hungarian Academy of Sciences, where he has founded the Parameterized Algorithms and Complexity group, funded from his European Research Council Starting and Consolidator Grants. In 2019-2020, he was a senior researcher at the Max Planck Institute for Informatics in Saarbrücken, and from 2020 faculty at CISPA Helmholtz Center for Information Security, Saarbrücken. Dániel is known for his theoretical work on algorithms and lower bounds for a wide range of problems.
Claire Mathieu
Title: Stable matchings beyond worst case
Abstract: Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated ``deferred acceptance'' algorithm for the problem. In the input, each participant ranks participants of the opposite type, so the input consists of a collection of permutations, representing the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The talk will discuss input models in which preference lists are correlated, and their implications about non-manipulability.
Bio: Claire Mathieu's research area concerns the design and analysis of algorithms, particularly the design of approximation algorithms for combinatorial optimization. She is a research director in Computer Science at CNRS. She was a recipient of the Computer Science Chair at College de France, participated in the design of the French Parcoursup platform for college admissions, received the 2019 CNRS Silver Medal, and belongs to the French Academy of Science.
Nobuko Yoshida
Title: Communicating Finite State Machines meet Multiparty Session Types
Abstract: Multiparty session types (MPST) provide a typing discipline for
message passing concurrency, ensuring deadlock freedom for distributed
processes.
I first summarise recent results and applications of MPST; then
explain a relationship between MPST and communicating finite state
machines (CFSMs), which offers not only theoretical justifications of
MPST but also a guidance to implement MPST in practice. I summarise
the recent results come from its relationship; and finally I show a
demo of one of the applications, NuScr, an extensible toolchain for
MPST-based multiparty protocols and its applications in programming
languages.
Nobuko Yoshida is Professor of Computing at Imperial College
London and EPSRC Career Established Fellowship.
Last 15 years, her main research interests are theories and
applications of protocols specifications and verifications. She
introduced multiparty session types in 2008 which received Most
Influential POPL Paper Award in 2018 (judged by its influence over the
last decade). This work enlarged the community and widened the scope
of applications of session types, e.g. runtime monitoring based on
Scribble (co-developed with Red Hat) has been deployed to other
projects such as cyberinfrastructure in the US Ocean Observatories
Initiative (OOI); and widened the scope of her research areas. She was
awarded CNRS and JSSP visiting fellowships and visiting professorships
at Paris VI and Paris VII.
She is an editor of ACM Transactions on
Programming Languages and Systems, Mathematical Structures in Computer Science, Journal of Logical Algebraic Methods in Programming, and the chief editor of The Computer-aided Verification and Concurrency Column for EATCS Bulletin. Her current industry partners include: Actyx,
Barclays, Cognizant, Red Hat, Weaveworks, ABB, EDF Energy, Xilinx,
EPCC Ltd, Codeplay Software Ltd and Mexeler. She received the Suffrage
Science Awards for Mathematics and Computing in 2020.
