Format results
- 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)
Coherent Gravitational Waveforms and Memory from Cosmic String Loops
Josu Aurrekoetxea University of Oxford
On the firewall puzzle
Beni Yoshida Perimeter Institute for Theoretical Physics
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.
Coherent Gravitational Waveforms and Memory from Cosmic String Loops
Josu Aurrekoetxea University of Oxford
We construct, for the first time, the time-domain gravitational-wave strain waveform from the collapse of a strongly gravitating Abelian Higgs cosmic string loop in full general relativity. We show that the strain exhibits a large memory effect during merger, ending with a burst and characteristic ringdown as a black hole is formed. Furthermore, we investigate the waveform and energy emitted as a function of width, radius and string tension Gμ. We find that the mass normalized gravitational-wave energy displays a strong dependence on the inverse of the string tension E_GW / M_0 ∝ 1/Gμ, with E_GW / M_0 ∼ O(1)% at the percent level, for the regime where Gμ ~ 1e-3 . Conversely, we show that the efficiency is only weakly dependent on the initial string width and initial string radii. Using these results, we argue that gravitational wave production is dominated by kinematical instead of geometrical considerations.
On the firewall puzzle
Beni Yoshida Perimeter Institute for Theoretical Physics
Many of previous approaches for the firewall puzzle rely on a hypothesis that interior partner modes are embedded on the early radiation of a maximally entangled black hole. Quantum information theory, however, casts doubt on this folklore and suggests a different tale; the outgoing Hawking mode will be decoupled from the early radiation once an infalling observer, with finite positive energy, jumps into a black hole. In this talk, I will provide counterarguments against current mainstream proposals and present an alternative resolution of the firewall puzzle which is consistent with predictions from quantum information theory. My proposal builds on the fact that interior operators can be constructed in a state-independent manner once an infalling observer is explicitly included as a part of the quantum system. Hence, my approach resolves a version of the firewall puzzle for typical black hole microstates as well on an equal footing.
Probing angular-dependent primordial non-Gaussianity from galaxy intrinsic alignments
Kazuyuki Akitsu University of Tokyo
The primordial non-Gaussianity (PNG) is a key feature to screen various inflationary models and it is one of the main targets in the next generation galaxy surveys. In particular, the local-type of PNG makes the galaxy bias scale-dependent in large-scales, which is known as the scale-dependent bias, allowing to constrain the local-type PNG from galaxy surveys. In this talk, I will present the galaxy shape correlation, called the ``intrinsic alignment'', can explore the angular-dependent PNG. Using N-body simulations, we show the angular-dependent PNG induces the scale-dependent bias in the intrinsic alignment, just as the angular-independent PNG leads to the scale-dependent bias in the galaxy number density correlation. By combining photometric and spectroscopic surveys to measure the intrinsic alignment, future galaxy surveys are potentially capable of constraining the angular-dependent PNG better than CMB experiments.