Sauganash East (14th floor), voco Chicago Downtown, an IHG Hotel

350 W Wolf Point Plaza Building 1, Chicago, IL 60654

Maria Florina (Nina) Balcan (Carnegie Mellon University)

Title: Machine Learning for Algorithm Design

Ravi Kannan (Simons Institute)

Title: Time, Space and Streaming Efficient Algorithms for Heavy Attentions

Xiaotie Deng and Hanyu Li (Peking University)

Title: Advancing Analysis of Approximate Nash Equilibria Algorithms by Machines

Abstract: The computation of approximate Nash equilibria (ANE) lies at the core of algorithmic game theory. Both the lower bounds and upper bounds of this problem are closely followed by the theory community. Since the landmark PPAD-completeness result for Nash equilibria in two-player normal-form games, significant research has focused on developing polynomial-time algorithms for ε-approximate Nash equilibria (ε-NE), with most focusing on two-player games.

We review all the techniques used to design ANE in the literature and show that they can be reformulated as so-called "search-and-mix" methods. With this new understanding, we develop a systematic approach to prove the tightness of an ANE algorithm. Specifically, we demonstrate the tightness of the previous state-of-the-art algorithm, the Tsaknakis-Spirakis (TS) algorithm, and the current state-of-the-art algorithm, the Deligkas-Fasoulakis-Markakis algorithm.

These insights further lead to a method that allows machines to automatically perform approximation analysis using a domain-specific language called LegoNE. LegoNE enables researchers to design algorithms with only high-level intuitions, while it automatically uncovers the underlying structures and proves the approximation bounds on its own. Using LegoNE, we design a new algorithm for three-player games that achieves a (0.56 + δ)-NE, improving the previous best bound (0.6 + δ). 

This demonstrates that human-machine collaboration can lead to higher-level understandings and better results.

Kyle Burke (Florida Southern College) and Matt Ferland (Dickinson College)

Title: Extroverted Play

Abstract: In this talk, we'll cover some of our results with Shang-Hua in Combinatorial Game Theory.  Shang-Hua jumped into this field feet-first in 2019 and he already has groundbreaking results in impartial and partizan games.

Shaddin Dughmi (University of Southern California)

Title: A Decade of Learning about Learning with Shang-Hua

Dan Spielman (Yale University)

Title: My collaboration with Shang-Hua

Christian Borgs (University of California, Berkeley)

Title: Is Local Information Enough to Predict an Epidemic?

Abstract: It is clear that the structure of our contact networks is important for the spread of an infection, with degree inhomogeneities and the related notion of super-spreaders being just the obvious reason. This raises the question of how much of the network we need to know about the network to make reliable predictions.

In this talk I discuss the question of whether knowledge of the local structure of a network is enough to predict the probability, size, and dynamics of an epidemic. More precisely, I discuss whether having access to randomly sampled nodes in the network and their neighborhoods, we can predict the above quantities.  This is joint research with Yeganeh Alimohammadi, Amin Saberi and Remco Van der Hofstad. 

Jin-Yi Cai (University of Wisconsin–Madison)

Title: Shor’s Algorithm Does Not Factor Large Integers in the Presence of Noise

Abstract: The talk will have two parts. In the first part we prove a theorem: If each quantum rotation gate has a vanishingly small amount of random noise, then Shor’s algorithm does not factor numbers of the form pq, where p and q satisfy the Fouvry property that p-1 and q-1 have large prime factors. These primes have a positive density. We also prove that the same theorem holds in the setting of random prime pairs. In the second part I speculate what this means and how one might address this. The paper can be found at https://link.springer.com/article/10.1007/s11432-023-3961-3.

Vahab Mirrokni (Google Research)

Title: Algorithms and Data@Scale: From Graphs to GenAI

Shang-Hua Teng (University of Southern California)

Title: Regularization, Heuristics, and Strategy: A Long Journey Towards Understanding a Few Fundamental yet Fuzzy Concepts in Computing

Abstract: "Thinking outside the box" has long been a defining trait of theoretical computer science. As a field, we value elegant theories, enlightening proofs, and insightful — sometimes unexpected — connections. However, we also look beyond theory to the practical world, seeking inspiration, establishing links, and explaining empirical trends. We aim for models that capture the essence of fundamental tasks, and for theories that shed insight on basic phenomena in computing.

In this talk, I will highlight how a long journey towards understanding a few fundamental, yet fuzzy, concepts in computing—specifically, “heuristics” (in algorithm design and AI), “regularization” (in machine learning), and “strategies” (in game and combinatorial game theory)—has led to the development of new conceptual frameworks, algorithmic techniques, and mathematical theories.

This represents joint work with many wonderful collaborators.

Dan Spielman (Yale University)

Xiaorui Sun (University of Illinois Chicago)