Format results
Towards Lorentzian quantum gravity via effective spin foams
Bianca Dittrich Perimeter Institute for Theoretical Physics
Minding the Gap: Lessons from LIGO-Virgo’s Biggest Black Holes
Maya Fishbach Canadian Institute for Theoretical Astrophysics (CITA)
Verification and Control of Partially Observable Probabilistic Systems
Gethin Norman (University of Glasgow)The infinite symmetries of black holes and other celestial stories
Laura Donnay SISSA International School for Advanced Studies
Games on Graphs: from Logic and Automata to Algorithms
Marcin Jurdziński (University of Warwick)Collisions of false-vacuum bubble walls in a quantum spin chain
Ashley Milsted California Institute of Technology
The black hole spectrum in supergravity
G. Joaquin Turiaci University of California, Santa Barbara
Introduction to Automata on Infinite Words
Orna Kupferman (Hebrew University)Explicit and Inexplicit higher form symmetries at quantum criticality
Cenke Xu University of California, Santa Barbara
A Tutorial on Logic, With an Emphasis on the Connections With Automata Theory
Mikolaj Bojańczyk (University of Warsaw)A new look at symmetries of 3d gravity
Marc Geiller École normale supérieure (ENS)
Unreasonable effectiveness of methods from theoretical computer science in quantum many-body physics
Anurag Anshu Harvard University
A central challenge in quantum many-body physics is a characterization of properties of `natural' quantum states, such as the ground states and Gibbs states of a local hamiltonian. The area-law conjecture, which postulates a remarkably simple structure of entanglement in gapped ground states, has resisted a resolution based on information-theoretic methods. We discuss how the right set of insights may come, quite unexpectedly, from polynomial approximations to boolean functions. Towards this, we describe a 2D sub-volume law for frustration-free locally-gapped ground states and highlight a pathway that could lead to an area law. Similar polynomial approximations have consequences for entanglement in Gibbs states and lead to the first provably linear time algorithm to simulate Gibbs states in 1D. Next, we consider the task of learning a Hamiltonian from a Gibbs state, where many-body entanglement obstructs rigorous algorithms. Here, we find that the effects of entanglement can again be controlled using tools from computer science, namely, strong convexity and sufficient statistics.
Towards Lorentzian quantum gravity via effective spin foams
Bianca Dittrich Perimeter Institute for Theoretical Physics
Euclidean quantum gravity approaches have a long history but suffer from a number of severe issues. This gives a strong motivation to develop Lorentzian approaches. Spin foams constitute an important such approach, which incorporate a rigorously derived discrete area spectrum. I will explain how this discrete area spectrum is connected to the appearance of an anomaly, which explains the significance of the Barbero-Immirzi parameter and forces an extension of the quantum configuration space, to also include torsion degrees of freedom. This can be understood as a defining characteristic of the spin foam approach, and provides a pathway to an (experimental) falsification.
All these features are captured in the recently constructive effective spin foam model, which is much more amenable to numerical calculations than previous models. I will present numerical results that a) show that spin foams do impose the correct equations of motion b) highlight the influence of the anomaly and c) underline the difference to Euclidean quantum gravity. I will close with an outlook on the features that can be studied with a truly Lorentzian model, e.g. topology change.
Minding the Gap: Lessons from LIGO-Virgo’s Biggest Black Holes
Maya Fishbach Canadian Institute for Theoretical Astrophysics (CITA)
Models for black hole formation from stellar evolution predict the existence of a pair-instability supernova mass gap in the range ~50 to ~120 solar masses. The binary black holes of LIGO-Virgo's first two observing runs supported this prediction, showing evidence for a dearth of component black hole masses above 45 solar masses. Meanwhile, among the 30+ new observations from the third observing run, there are several black holes that appear to sit above the 45 solar mass limit. I will discuss how these unexpectedly massive black holes fit into our understanding of the binary black hole population. The data are consistent with several scenarios, including a mass distribution that evolves with redshift and the possibility that the most massive binary black hole, GW190521, straddles the mass gap, containing an intermediate-mass black hole heavier than 120 solar masses.
Verification and Control of Partially Observable Probabilistic Systems
Gethin Norman (University of Glasgow)In this talk I will outline automated techniques for the verification and control of partially observable probabilistic systems for both discrete and dense models of time. For the discrete-time case, we formally model these systems using partially observable Markov decision processes; for dense time, we propose an extension of probabilistic timed automata in which local states are partially visible to an observer or controller. Quantitative properties of interest, relate to the probability of an event’s occurrence or the expected value of some reward measure. I will present techniques to either verify that such a property holds or to synthesise a controller for the model which makes it true. The approach is based on an integer discretisation of the model’s dense-time behaviour and a grid-based abstraction of the uncountable belief space induced by partial observability. The latter is necessarily approximate since the underlying problem is undecidable, however both lower and upper bounds on numerical results can be generated.The infinite symmetries of black holes and other celestial stories
Laura Donnay SISSA International School for Advanced Studies
In this talk, I will review the recent advances in the understanding of intriguing infinite-dimensional symmetries that emerge at the boundary of asymptotically flat spacetime and in the vicinity of black hole horizons. These symmetries play an important role in the description of many phenomena such as gravitational memory effects and scattering amplitudes, and have paved the way to a holographic description of gravity in asymptotically flat spacetimes in terms of correlators on the celestial sphere.
Games on Graphs: from Logic and Automata to Algorithms
Marcin Jurdziński (University of Warwick)Game theory has been forged in the 1944 book of von Neumann (a mathematician) and Morgenstern (an economist) as a way to reason rigorously about economic behaviour, but its methodologies have since also illuminated many areas of social, political, and natural sciences. More recently, it has also enjoyed fruitful cross-fertilization with Computer Science, yielding the vibrant areas of Algorithmic Game Theory and Algorithmic Mechanism Design. Less broadly known, but relevant to the Theoretical Foundations of Computer Systems program at Simons, are the game theoretic models that originate from set theory, logic, and automata. In this tutorial, we consider a very basic model of games on graphs. We then argue that this simple model is general enough to encompass a range of classic game-theoretic models, and that it can streamline or enable solutions of notable problems, for example: - Gale-Stewart games in set theory and Martin’s Borel determinacy theorem; - Church’s reactive synthesis problem and its solution by Buchi and Landweber; - Rabin’s tree theorem and its proof using positional determinacy; - Pnueli and Rosner’s temporal synthesis problem; - evaluating nested Knaster-Tarski fixpoints; - the complexity of pivoting rules in linear optimization and stochastic planning; - star height problem. The technical focus of this tutorial is on the algorithmic aspects of one relatively simple but influential graph game model called parity games. Building efficient parity game solvers is worthwhile because many model-checking, equivalence-checking, satisfiability, and synthesis problems boil down to solving a parity game. The problem has an intriguing computational complexity status: it is both in NP and in co-NP, and in PLS and PPAD, and hence unlikely to be complete for any of those complexity classes; no compelling evidence of hardness is known; and it is a long-standing open problem if it can be solved in polynomial time. A key parameter that measures the descriptive complexity of a parity game graph is the number of distinct priorities; for example, in games arising from nested Knaster-Tarski fixpoint expressions, it reflects the number of alternations between least and greatest fixpoints. All known algorithms for several decades have been exponential in the number of priorities, until 2017 when Calude, Jain, Khoussainov, Li, and Stephan made a breakthrough by showing that the problem is FPT and that there is a quasi-polynomial algorithm. In 2018, Lehtinen has proposed another parameter called the register number and has shown that parity games can be solved in time exponential in it. This refines the quasi-polynomial complexity obtained by Calude et al. because the register number of a finite game is at most logarithmic in its size. We argue that the register number coincides with another parameter called the Strahler number, which provides structural insights and allows to solve parity games efficiently using small Strahler-universal trees. We mention preliminary experimental evidence to support Lehtinen’s thesis that most parity games in the wild have very tiny register/Strahler numbers. This strengthens a popular belief that finding a polynomial-time algorithm is more vital in theory than in practice and it suggests practical ways of turning modern quasi-polynomial algorithms into competitive solvers.Collisions of false-vacuum bubble walls in a quantum spin chain
Ashley Milsted California Institute of Technology
We study the real-time dynamics of a small bubble of "false vacuum'' in a quantum spin chain near criticality, where the low-energy physics is described by a relativistic (1+1)-dimensional quantum field theory. Such a bubble can be thought of as a confined kink-antikink pair (a meson). We carefully construct bubbles so that particle production does not occur until the walls collide. To achieve this in the presence of strong correlations, we extend a Matrix Product State (MPS) ansatz for quasiparticle wavepackets [Van Damme et al., arXiv:1907.02474 (2019)] to the case of confined, topological quasiparticles. By choosing the wavepacket width and the bubble size appropriately, we avoid strong lattice effects and observe relativistic kink-antikink collisions. We use the MPS quasiparticle ansatz to identify scattering outcomes: In the Ising model, with transverse and longitudinal fields, we do not observe particle production despite nonintegrability (supporting recent numerical observations of nonthermalizing mesonic states). With additional interactions, we see production of confined and unconfined particle pairs. Although we simulated these low-energy, few-particle events with moderate resources, we observe significant growth of entanglement with energy and with the number of collisions, suggesting that increasing either will ultimately exhaust our methods. Quantum devices, in contrast, are not limited by entanglement production, and promise to allow us to go far beyond classical methods. We anticipate that kink-antikink scattering in 1+1 dimensions will be an instructive benchmark problem for relatively near-term quantum devices.
The black hole spectrum in supergravity
G. Joaquin Turiaci University of California, Santa Barbara
The talk will focus on the spectrum of near-extremal black holes in gravity and near-BPS black holes in supergravity. For concreteness, we will study cases in asymptotically four-dimensional flat space and three-dimensional Anti-de Sitter. This will be done by analyzing quantum effects near the horizon captured by an emergent Jackiw-Teitelboim mode at low temperatures. This will allow us to systematically study questions such as the extremal degeneracy and the size of the gap in the black hole spectrum, which can be compared to some string theory constructions.
Introduction to Automata on Infinite Words
Orna Kupferman (Hebrew University)Automata on infinite words have applications in system specification, verification, and synthesis. We introduce Buchi automata, and survey interesting issues around their closure properties, expressive power, determinization, and decision problems. Below you can find Panopto links to Orna's pre-recorded talks: Part 1: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=88f4fcfc-e531-404e-bdb2-acb100a573b2 Part 2: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=5396c12c-ecff-40c5-8afc-acb100a56ed2 Part 3: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=b37fc8b9-05ef-42bb-99ca-acb100c1fc64 Part 4: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=262825e9-479e-4e7a-9386-acb30076b006 Part 5: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=257dd520-bd68-4dac-95e6-acb30088cce8 Part 6: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=7ed603a9-ce88-46ff-ae43-acb30095a97bExplicit and Inexplicit higher form symmetries at quantum criticality
Cenke Xu University of California, Santa Barbara
Recent years new concepts of symmetries have been developed such as higher form symmetries, and categorical symmetries. The higher form symmetries can be either explicit in a Hamiltonian, or inexplicit as a dual of an ordinary symmetry. The behavior of higher form symmetries are easy to evaluate in phases with gaps. But at quantum criticalities their behaviors are more nontrivial. We evaluate the behaviors of higher form symmetries (either explicit or inexplicit) at various quantum critical points, and demonstrate that for many quantum critical points a universal logarithmic contribution arises, which is analogous to the quantum entanglement entropy. This logarithmic contribution is related to the universal conductance at the quantum critical points, and in some cases can be computed exactly using duality between CFTs developed in last few years. We also evaluate the behavior of categorical symmetries for more exotic cases with subsystem symmetries.
A Tutorial on Logic, With an Emphasis on the Connections With Automata Theory
Mikolaj Bojańczyk (University of Warsaw)This is a 3 part tutorial about logic. It is organised around algorithms for checking if a formula is true in a model.There are two central variants of this problem. In the model checking problem we are given the model and the formula, and we want to know it the formula is true in the model. In the satisfiability (dually, validity) problem we are only given the formula, and we want to know if it is true in some (dually, every) model (perhaps from some fixed class of models). There are three parts of the tutorial (each set of slides contains a soundtrack): Part 1 (slides ) discusses the variant of the model checking problem where the model is fixed and only the formula is given on the input. (This is also known as deciding the theory of the model.) I will particularly focus on cases where the problem can be solved using automata, and hence the corresponding logic is going to be monadic second-order logic, which is an old friend of automata. Part 2 (slides) discusses the satisfiability problem. Here, again, the main focus is on variants of the problem that can be solved using automata, namely monadic second-order logic on words, trees and graphs of bounded treewidth. Part 2 (slides), soundtrack coming Jan 20 morning) discusses the variant of the model checking problem where the formula is fixed and the model is the input. Apart from results that use automata (mainly Courcelle’s theorem about MSO model checking on graphs of bounded treewidth), I will also discuss some results about first-order logic on sparse graph classes.A new look at symmetries of 3d gravity
Marc Geiller École normale supérieure (ENS)
I will review the analysis of boundary symmetries in first order 3d gravity, and explain how the study of the boundary current algebra and the Sugawara construction actually leads to two dual notions of diffeomorphism charges. This provides a new understanding of the relationship between the second order and first order formulations, and of the existence of finite distance asymptotic symmetries (as strange as this sounds) in topological theories. This analysis is performed on the most general theory of first order 3d gravity, which also enables to understand the duality between curvature and torsion, as well as the relationship with chiral and massive gravity.