Extroverted Theory
A Celebration of Shang-Hua Teng's 60th Birthday
October 27th, 2024, 9am-5pm
FOCS 2024 Workshop
A Celebration of Shang-Hua Teng's 60th Birthday
October 27th, 2024, 9am-5pm
FOCS 2024 Workshop
Professor Shang-Hua Teng has been a leading figure in theoretical computer science for many years, making deep and lasting contributions to an extraordinary range of research areas, including algorithms, spectral graph theory, computational economics and game theory, and combinatorial optimization. Additionally, he has worked to develop theory that is meaningful in other fields and helps explain empirical observations.
This workshop will bring together leading researchers in computer science to celebrate Shang-Hua's 60th birthday. It will feature survey talks and research talks on topics related to his work, as well as discussions on his philosophy of research and the role of theory in computer science.
Location
Sauganash East (14th floor), voco Chicago Downtown, an IHG Hotel
350 W Wolf Point Plaza Building 1, Chicago, IL 60654
Agenda
9am-9:05am
Opening Remarks
9:05am - 9:30am
Maria Florina (Nina) Balcan, "Machine Learning for Algorithm Design"
9:30am - 10am
Ravi Kannan, "Time, Space and Streaming Efficient Algorithms for Heavy Attentions"
10am -10:30am
Xiaotie Deng and Hanyu Li, "Advancing Analysis of Approximate Nash Equilibria Algorithms by Machines"
10:30am - 11am
Break
11am - 11:30am
Kyle Burke and Matt Ferland, "Extroverted Play"
11:30am - 12pm
Shaddin Dughmi, "A Decade of Learning about Learning with Shang-Hua"
12pm - 2pm
Graduating Bits and Conference Lunch
2pm - 2:30pm
Dan Spielman, "My collaboration with Shang-Hua"
2:30pm - 3pm
Christian Borgs, "Is Local Information Enough to Predict an Epidemic?"
3pm - 3:30pm
Jin-Yi Cai, "Shor’s Algorithm Does Not Factor Large Integers in the Presence of Noise"
3:30pm - 4pm
Break
4pm - 4:30pm
Vahab Mirrokni, "Algorithms and Data@Scale: From Graphs to GenAI"
4:30pm - 5pm
Shang-Hua Teng, "Regularization, Heuristics, and Strategy: A Long Journey Towards Understanding a Few Fundamental yet Fuzzy Concepts in Computing"
Abstracts
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.
Organizers
Dan Spielman (Yale University)
Xiaorui Sun (University of Illinois Chicago)