Format results
- Ryan Williams (MIT)
Total Function Problems in the Polynomial Hierarchy
Christos Papadimitriou (Columbia University)Structure of SAT Instances
Jordi Levy (Artificial Intelligence Research Institute, Spanish National Research Council), Stefan Szeidar (TU Wien), and Ralf Rothenberger (University of Potsdam)Area law, topological quantum field theory, and the quantum marginal problem
Isaac Kim University of California, Davis
Axion Cosmic Strings: Players in the Early Universe?
Michael Dine Institute for Advanced Study (IAS) - School of Natural Sciences (SNS)
Combining SAT and Computer Algebra for Circuit Verification
Daniela Kaufmann (Johannes Kepler University Linz)Constraining Early Dark Energy with Large Scale Structure
Evan McDonough University of Winnipeg
Floquet spin chains and the stability of their edge modes
Aditi Mitra New York University (NYU)
Supersymmetry and RCHO revisited
Paul Townsend University of Cambridge
Searching for Dark Matter with Superconducting Qubits - Akash Dixit
Akash Dixit University of Chicago
Melonic field theories
Dario Benedetti Ecole Polytechnique - CPHT
On the Usefulness of the Strong Exponential Time Hypothesis
Ryan Williams (MIT)Over the past 15 years or so, the Strong Exponential Time Hypothesis (SETH) has been very useful for proving conditional hardness for many problems: it's a problem at the heart of fine-grained complexity. In this talk, I will discuss another way in which SETH has been useful.Total Function Problems in the Polynomial Hierarchy
Christos Papadimitriou (Columbia University)The empty pigeonhole principle asserts that, if there are more pigeonholes than pigeons, one pigeonhole must be empty. The corresponding class of total function problems contains all of FNP, and its natural problems include applications of the union bound and several well known explicit constructions. Higher up in the polynomial hierarchy, one finds total function problems related to tournaments and the Sauer-Shelah lemma.Approaches to Scattering in Quantum Gravity and Gauge Theory from Symmetry
Monica Pate Harvard University
The problem of quantum gravity -- i.e. to determine the microscopic structure underlying quantum mechanical theories that reproduce general relativity at long distances -- is a major outstanding problem in modern physics. Solving the quantum gravitational scattering problem is one sharp way to address this question. While in principle effective field theory (EFT) provides a systematic framework for solving scattering problems, in quantum gravity the complete answer requires an infinite number of measurements and thereby fails to predict details of the microscopic structure.
I will present two developments that provide new insight into the gravitational scattering problem. The first is a class of infinite-dimensional symmetries generically found to arise in gauge and gravitational scattering. The infinite number of constraints implied by the symmetries are equivalent to quantum field theoretic soft theorems, which prescribe the pattern of soft radiation produced during a scattering event. The second development is a reformulation of the gravitational scattering problem in which Lorentz symmetry is rendered manifest and realized as the action of the global conformal group in two dimensions. This reformulation, which involves scattering particles of definite boost weight as opposed to energy, offers a new approach precisely because it does not admit the decoupling of low and high-energy physics that underpins the traditional EFT approach. I will describe new perspectives ensuing from these developments on various properties of the gravitational scattering problem, including collinear limits, infrared divergences and universal behavior associated to black hole formation.
Structure of SAT Instances
Jordi Levy (Artificial Intelligence Research Institute, Spanish National Research Council), Stefan Szeidar (TU Wien), and Ralf Rothenberger (University of Potsdam)Topics: Jordi Levy: On the Formal Characterization of Industrial SAT Instances Abstract: Over the last 20 years, SAT solvers have experienced a great improvement in their efficiency when solving practical or industrial SAT problems. This success is surprising, considering that SAT is an NP-complete problem. Over the years, the particular structure of industrial instances has been proposed, informally, as a reason. This has led, for instance, the organizers of the SAT competition to distinguish two tracks, random and industrial, and solvers wining in one track have a poor performance on the other, and vice versa. We think that a better characterization of this structure may be decisive in future improvements of practical SAT solving. During my talk, I'll start revisiting the notions that try to characterize how difficult is to be solved a SAT instance in practice, especially, the notion of "hardness" or tree-like space resolution. I'll discuss some properties that are shared by most industrial SAT instances used in the SAT competition, such as scale-free structure, high modularity, and low fractal dimension, and how these features may influence the performance of practical SAT solvers. I'll finish introducing some models of random SAT instances that try to reproduce these characteristics. Stefan Szeidar: Algorithmic utilization of structure in SAT instances Abstract: In this talk, I will survey various concepts that have been proposed to capture the hidden structure in SAT instances. I will focus on concepts that provide worst-case runtime guarantees for SAT algorithms and discuss a suitable theoretical framework. I will also discuss how these concepts relate to each other and propose questions for further research. Some of the talk's content is covered by the extended and updated Chapter 17, Fixed-Parameter Tractability, of the Handbook of Satisfiability, 2nd edition, 2021. Ralf Rothenberger: Structural Parameters - Heterogeneity and Geometry Abstract: Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. In this talk I present our most recent results trying to understand the impact of these two properties on SAT by studying the resolution proof size of random k-SAT models that allow to control heterogeneity and locality.Area law, topological quantum field theory, and the quantum marginal problem
Isaac Kim University of California, Davis
Many physical states of interest, such as ground states of gapped quantum many-body systems, are expected to obey an area law of entanglement entropy. I will report on a series of recent results that suggest a deep connection between area law and two seemingly unrelated subjects: topological quantum field theory and quantum marginal problem. Recently, we deduced --- only using area law and quantum information-theoretic tools --- the existence of new topological charges and invariants associated with the domain walls between topologically ordered systems in two spatial dimensions. Moreover, the same set of tools were also used in finding a solution to the quantum marginal problem. This is the problem in which one asks whether a set of reduced density matrices on bounded subsystems are compatible with some globally well-defined many-body quantum state. Since this problem was first posed in 1959, a solution that goes beyond the mean-field ansatz has remained elusive until now. These results suggest that area law is not just a qualitative statement about entanglement; it is an important equation that lets us "solve" quantum many-body systems that appear in nature.
Based on arXiv:2008.11793 and arXiv:2010.07424
Axion Cosmic Strings: Players in the Early Universe?
Michael Dine Institute for Advanced Study (IAS) - School of Natural Sciences (SNS)
Axion cosmic strings have for some time been considered a potential source of enhancement of axion dark matter production, and have been the subject of extensive simulations (for references, see out in recent years). But axion strings are rather peculiar entities. This talk will explore some aspects of these objects, and suggest that they are not likely to play a distinguished role in early universe cosmology.
Combining SAT and Computer Algebra for Circuit Verification
Daniela Kaufmann (Johannes Kepler University Linz)Even more than 25 years after the Pentium FDIV bug, automated verification of arithmetic circuits, and most prominently gate-level integer multipliers, still imposes a challenge. Approaches which purely rely on SAT solving or on decision diagrams seem to be unable to solve this problem in a reasonable amount of time. In this talk, we will demonstrate a verification technique that is based on algebraic reasoning and is currently considered to be one of the most successful verification techniques for circuit verification. In this approach the circuit is modelled as a set of polynomial equations. For a correct circuit we need to show that the specification is implied by the polynomial representation of the given circuit. However parts of the multiplier, i.e., final stage adders, are hard to verify using only computer algebra. We will present a hybrid approach which combines SAT and computer algebra to tackle this issue.Constraining Early Dark Energy with Large Scale Structure
Evan McDonough University of Winnipeg
The Hubble tension is conventionally viewed as that between the cosmic microwave background (CMB) and the SH0ES measurement. A prominent proposal for a resolution of this discrepancy is to introduce a new component in the early universe, which initially acts as "early dark energy" (EDE), thus decreasing the physical size of the sound horizon imprinted in the CMB and increasing the inferred H_0, bringing it into near agreement with SH0ES. However, this impacts cosmological observables beyond the CMB -- in particular, the large scale structure (LSS) of the universe across a range of redshift. The H_0 tension resolving EDE cosmologies produce scale-dependent changes to the matter power spectrum, including 10% more power at k=1 h/Mpc. Motivated by this, I will present the results of two analyses of LSS constraints on the EDE scenario. Weak lensing and galaxy clustering data (from, e.g., the Dark Energy Survey) significantly constrain the EDE model, and the resulting H_0 is in significant tension with SH0ES. Complementary to this, including data from the Baryon Oscillation Spectroscopic Survey (BOSS), analyzed using the effective field theory (EFT) of LSS, yields an EDE H_0 value that is in significant (3.6\sigma) tension with SH0ES. These results indicate that current LSS data disfavours the EDE model as a resolution of the Hubble tension, and, more generally, that the EDE model fails to restore cosmological concordance. A sensitivity forecast for EUCLID suggests that future LSS surveys can close the remaining parameter space of the model.
Floquet spin chains and the stability of their edge modes
Aditi Mitra New York University (NYU)
In this talk I will begin by introducing symmetry protected topological (SPT) Floquet systems in 1D. I will describe the topological invariants that characterize these systems, and highlight their differences from SPT phases arising in static systems. I will also discuss how the entanglement properties of a many-particle wavefunction depend on these topological invariants. I will then show that the edge modes encountered in free fermion SPTs are remarkably robust to adding interactions, even in disorder-free systems where generic bulk quantities can heat to infinite temperatures due to the periodic driving. This robustness of the edge modes to heating can be understood in the language of strong modes for free fermion SPTs, and almost strong modes for interacting SPTs.
I will then outline a tunneling calculation for extracting the long lifetimes of these edge modes by mapping the Heisenberg time-evolution of the edge operator to dynamics of a single particle in Krylov space.
Supersymmetry and RCHO revisited
Paul Townsend University of Cambridge
Various links between supersymmetry and the normed division algebras R,C,H,O were found in the 1980s. This talk will focus on the link between K=R,C,H,0 and supersymmetric field theories in a Minkowski spacetime of dimension D=3,4,6,10. The first half will survey the history starting with a 1944/5 paper of Dirac and heading towards the links found in 1986/7 between R,C,H,O and super-Yang-Mills theories. The second half will review a result from 1993 that connects, via a twistor-type transform, the superfield equations of super-Maxwell theory in D=3,4,6,10 to a K-chirality constraint on a K-valued worldline superfield of N=1,2,4,8 worldline supersymmetry. This provide an explicit connection of octonions to the free-field D=10 super-Maxwell theory.Searching for Dark Matter with Superconducting Qubits - Akash Dixit
Akash Dixit University of Chicago
Detection mechanisms for low mass bosonic dark matter candidates, such the axion or hidden photon, leverage potential interactions with electromagnetic fields, whereby the dark matter (of unknown mass) on rare occasion converts into a single photon. Current dark matter searches operating at microwave frequencies use a resonant cavity to coherently accumulate the field sourced by the dark matter and a near standard quantum limited (SQL) linear amplifier to read out the cavity signal. To further increase sensitivity to the dark matter signal, sub-SQL detection techniques are required. Here we report the development of a novel microwave photon counting technique and a new exclusion limit on hidden photon dark matter. We operate a superconducting qubit to make repeated quantum non-demolition measurements of cavity photons and apply a hidden Markov model analysis to reduce the noise to 15.7 dB below the quantum limit, with overall detector performance limited by a residual background of real photons. With the present device, we perform a hidden photon search and constrain the kinetic mixing angle to ≤ 1.68×10−15 in a band around 6.011 GHz (24.86 μeV) with an integration time of 8.33 s. This demonstrated noise reduction technique enables future dark matter searches to be sped up by a factor of 1300. By coupling a qubit to an arbitrary quantum sensor, more general sub-SQL metrology is possible with the techniques presented in this work.
Melonic field theories
Dario Benedetti Ecole Polytechnique - CPHT
The melonic limit of a field theory is a large-N limit in which melonic diagrams dominate, thus differing significantly from the cactus and planar limits of vector and matrix models. It was first discovered in tensor models in zero dimensions, viewed as an approach to quantum gravity, and later in the SYK model. More recently, it has found applications in quantum field theory on a fixed (flat) background as an analytic tool for the study of new fixed points of the renormalization group, i.e. new conformal field theories. In this talk, I will review the main features of the melonic limit, and in view of the recent developments I will revisit an old model by Amit and Roginsky with SO(3) internal symmetry, which is neither a tensor model nor a disordered model like SYK, and yet it has a similar melonic limit. Time permitting, I will also comment on similarities with the fishnet model by Kazakov et al, and on the (in)stability of all such models when complex scaling dimensions appear.