Keynote Speakers

Abstract: In the study of adaptive optimization, adaptive submodularity plays an important role. Just as in the nonadaptive case, it is closely related to the performance of the greedy algorithm. In 2011, Golovin and Krause discovered that the influence maximization in a social network with myopic feedback model is not adaptive submodular. Despite this, they conjectured that the greedy algorithm still has a good performance; this conjecture was proved in 2019 by Peng and Chen. In this lecture I shall present a newly published solution, which relies heavily on a surprising connection between adaptivity and nonadaptivity on social influence maximization.

Bio: Ding-Zhu Du received his Master’s degree in 1982 from the Chinese Academy of Sciences and Ph.D. in 1985 from the University of California at Santa Barbara. His research areas include optimization theory and mathematical foundation of computer science. As a researcher in mathematics and theoretical computer science, he has held positions with MSRI (Berkeley), MIT, Chinese Academy of Sciences, Princeton University, University of Minnesota, and NSF of USA; he is now a professor at the University of Texas at Dallas. He has spent leaves of absence at various institutions, such as Korea University, City University of Hong Kong, and Xi’an Jiaotong University. He has published over 260 journal papers and 10 books and has served on editorial boards of 15 international journals. He was granted the Natural Science Prize (First Class) of the Chinese Academy of Sciences in 1992, the National Natural Science Prize (Second Class) of China in 1993, and the CSTS award of INFORMS in 1998.

Abstract: Automated market makers (AMMs) are automata that trade assets on one or more distributed ledgers. Arbitrage agents typically keep their prices in line with prices set by a shared central reference market. What if the system were truly decentralized, with no shared reference market? Consider a distributed system where a population of AMMs interact with a population of arbitrage agents. These agents seek to profit from pairwise price differences between randomly-chosen AMMs. We give bounds on convergence rates, arbitrage profits, and the degree to which arbitrageurs can collude to set prices. What if AMMs could capture arbitrage profits for themselves by rebalancing their pools directly? Such a service could be provided as a kind of insurance. We give bounds on convergence rates, and the degree to which the AMMs can collude to set prices. This talk is intended for a general audience. Joint work with Sergio Rajsbaum and Sam Devorsetz.

Bio: Maurice Herlihy has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University and the staff of DEC Cambridge Research Lab. He is the recipient of the 2003 Dijkstra Prize in Distributed Computing, the 2004 Gödel Prize in theoretical computer science, the 2008 ISCA influential paper award, the 2012 Edsger W. Dijkstra Prize, and the 2013 Wallace McDowell award. He received a 2012 Fulbright Distinguished Chair in the Natural Sciences and Engineering Lecturing Fellowship, and he is fellow of the ACM, a fellow of the National Academy of Inventors, the National Academy of Engineering, and the National Academy of Arts and Sciences. In 2022, he won his third Dijkstra Prize.

Abstract: Improving algorithms via predictions is a very active research topic in recent years. We initiates the systematic study of mechanism design in this model. In a number of well-studied mechanism design settings, we make use of imperfect predictions to design mechanisms that perform much better than traditional mechanisms if the predictions are accurate (consistency), while always retaining worst-case guarantees even with very imprecise predictions (robustness).

Bio: Dr. Pinyan Lu is a professor and the founding director of Institute for Theoretical Computer Science at Shanghai University of Finance and Economics (ITCS@SUFE). Before joining SUFE, he spent seven years as a researcher at Microsoft Research. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focused on complexity and approximability of counting problems, and algorithmic mechanism design. Pinyan Lu is the recipient of a number of awards including ICCM Silver Medal of Mathematics, Distinguished Membership of ACM and CCF, CCF Young Scientist award, Best Paper Award from ICALP 2007, FAW 2010, ISAAC 2010 and so on. He is the PC chairs for FAW-AAIM 2012, WINE 2017, FAW 2018, ISAAC 2019 and so on, and PC members for STOC, FOCS, SODA and a dozen of international conferences. He is an Editorial Board Member of the “Information and Computation” and "Theoretical Computer Science".