Motivation
A casual gathering for theorists to chat, exchange ideas and have fun!
Topics
Quantum Computing, Learning Theory and Online Algorithms
Schedule
| 9:00am - 9:45am | Noncommutativity, CSPs, and Quantum Computation | |
| By Hamoon Mousavi from Berkeley 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. |
||
| 9:45am - 10:30am | On the Sudden Death of Thermal Entanglement | |
| By Ainesh Bakshi from MIT 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. |
||
| 10:30am - 11:00am | Coffee Break |
|
| 11:00am - 11:45am | On Supervised Learning and Bipartite Matching | |
| By Shaddin Dughmi from USC Abstract. I will describe some recent joint results on the theory of supervised learning which follow from connections to bipartite matching on infinite graphs. This is based on a series of joint work with Julian Asilis, Siddartha Devic, Vatsal Sharan, and Shang-Hua Teng, all at USC. |
||
| 11:45am - 12:30am | Online Stochastic Correlated Selection | |
| By Zhiyi Huang from HKU 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. |
||
| 12:30pm | Group Lunch |
|