[Theory] Theory talks next week

[Madhur Tulsiani via Theory]

Hi all,

Just wanted to point out that next week is quite an action-packed one in terms of theory talks, with some amazing speakers! This includes talks on Monday by Nina Balcan and Christos Papadimitriou, a mini-workshop on Thursday, and of course FOCS which is happening in Chicago downtown: https://focs.computer.org/2024/

Here are some details of the talks happening in Hyde Park:

- Nina Balcan: Online learning in Stackelberg Security Games (Monday 11:00 am, in TTIC Room 530)

- Christos Papadimitriou: Game Dynamics As The Meaning Of The Game (Monday 3:00 pm, in Eckart Hall Room 202)

- Post-FOCS mini workshop (https://www.haifeng-xu.com/post-focs24/index.html) Thursday 9-12:30 in JCL 298, with talks listed below

	- Hamoon Mousavi: Noncommutativity, CSPs, and Quantum Computation 
	- Ainesh Bakshi: On the Sudden Death of Thermal Entanglement
	- Shaddin Dughmi: Title TBD
	- Zhiyi Huang: Online Stochastic Correlated Selection

Abstracts are included below in case you want to take a look. 

Best,
Madhur 

==

Speaker: Nina Balcan

Title: Online learning in Stackelberg Security Games (CMU)

Abstract: In a Stackelberg Security Game, a defender commits to a randomized deployment of security resources, and an attacker best responds by attacking a target that maximizes their utility. While algorithms for computing an optimal strategy for the defender to commit to have been used in several real-world applications, deployed applications require knowledge about the utility function of the potential attacker. In this talk I will describe an online learning approach for addressing this problem. We consider algorithms that prescribe a randomized strategy for the defender at each step against an adversarially chosen sequence of attackers and obtain feedback on their choices. I will discuss online algorithms whose regret (when compared to the best fixed strategy in hindsight) is sublinear in the number of time steps. I will also consider an extension that handles auxiliary contextual information that is often readily available to each player (e.g. traffic patterns or weather conditions) and discuss what no regret guarantees are possible in this even more realistic scenario.

—

Speaker: Christos Papadimitriou (Columbia University)

Title: Game Dynamics As The Meaning Of The Game

Abstract:  The modern era of game theory started with Nash's theorem in 1950, establishing that all finite games have a stable solution from which players will not deviate. When computer scientists embraced game theory four decades later, computational flaws of this concept came under scrutiny: The Nash equilibrium is not unique, and it is intractable to find one.  I will recount how three theorems, serendipitously proved during this past year, suggest an alternative meaning of the game:  A game can be seen as a mapping from a prior distribution of the players' behavior to the limit distribution under the dynamics of repeated play, and reasonable variants of this mapping can be computed efficiently.

—

Speaker: Hamoon Mousavi (UC Berkeley)

Title: Noncommutativity, CSPs, and Quantum Computation

Abstract. Classical constraint satisfaction problems, such as 3SAT and MaxCut, have two important generalizations in quantum information. One leads to the Local Hamiltonian problem, and the other to Nonlocal Games. These frameworks hold fascinating physical and computational aspects. Computationally, the Local Hamiltonian problem naturally characterizes QMA (the quantum analogue of NP), while Nonlocal Games capture RE (the class of recursively enumerable languages containing all computable languages and more). From a physical perspective, Hamiltonians formalize interactions between particles in a quantum system, while Nonlocal Games encode the notion of quantum correlations. In this talk, I will explore these quantum CSPs, share recent results, and highlight several intriguing open problems.

—

Speaker: Ainesh Bakshi (MIT)

Title: On the Sudden Death of Thermal Entanglement 

Abstract: Entanglement is the crucial phenomenon that distinguishes quantum systems from classical ones. Specifically, we consider entanglement in many-body systems at thermal equilibrium as a function of the temperature. Systems at thermal equilibrium at sufficiently low temperatures are demonstrably entangled. We investigate whether these systems remain entangled as the temperature increases. We prove that above a fixed constant temperature, the system does not exhibit any entanglement and behaves entirely classically. This proof of the sudden death of thermal entanglement cuts against a large body of prior work, both rigorous and computational, which only gives mild limits on entanglement at constant temperatures. Our proof falls out of a new connection between lack of entanglement and an algorithm for preparing thermal states on a quantum computer. 

Based on joint work with Allen Liu, Ankur Moitra and Ewin Tang.

—

Speaker: Shaddin Dughmi (USC)

Title/Abstract: TBD

—


Speaker: Zhiyi Huang (HKU)

Title: Online Stochastic Correlated Selection 

Abstract: We initiate the study of Stochastic Online Correlated Selection (SOCS), a family of online rounding algorithms for the general Non-IID model of Stochastic Online Submodular Welfare Maximization and its special cases such as unweighted and vertex-weighted Online Stochastic Matching, Stochastic AdWords, and Stochastic Display Ads. Following this framework, we make progress on numerous problems such as online stochastic matching, query-commit matching, stochastic display ads and also answer two open questions related to AdWords: 

- Stochastic AdWords: We give a 0.6338 competitive algorithm for Stochastic AdWords, breaking the 1-1/e barrier for the first time, answering a decade-long open question 

- AdWords: we get the first multi-way online correlated section (OCS) for AdWords, addressing an open question in the OCS literature.

==