Search

We consider sampling in the so-called low-temperature regime, which is typically characterised by non-local behaviour and strong global correlations. Canonical examples include sampling independent sets on bipartite graphs and sampling from the ferromagnetic $q$-state Potts model. Low-temperature sampling is computationally intractable for general graphs, but recent advances based on the polymer method have made significant progress for graph families that exhibit certain expansion properties that reinforce the correlations, including for example expanders, lattices and dense graphs. One of the most natural graph classes that has so far escaped this algorithmic framework is the class of sparse Erd\H{o}s-R\'enyi random graphs whose expansion only manifests for sufficiently large subsets of vertices; small sets of vertices on the other hand have vanishing expansion which makes them behave independently from the bulk of the graph and therefore weakens the correlations. At a more technical level, the expansion of small sets is crucial for establishing the Kotecky-Priess condition which underpins the applicability of the framework. Our main contribution is to develop the polymer method in the low-temperature regime for sparse random graphs. As our running example, we use the Potts and random-cluster models on $G(n,d/n)$ for $d=\Theta(1)$, where we show a polynomial-time sampling algorithm for all sufficiently large $q$ and $d$, at all temperatures. Our approach applies more generally for models that are monotone. Key to our result is a simple polymer definition that blends easily with the connectivity properties of the graph and allows us to show that polymers have size at most $O(\log n)$.

Consider a $k$-SAT formula $\Phi$ where every variable appears at most $d$ times, and let $\sigma$ be a satisfying assignment of $\Phi$ sampled proportionally to $e^{\beta m(\sigma)}$ where $m(\sigma)$ is the number of variables set to true and $\beta$ is a real parameter. Given $\Phi$ and $\sigma$, can we learn the value of $\beta$ efficiently? This problem falls into a recent line of works about single-sample ("one-shot") learning of Markov random fields. The $k$-SAT setting we consider here was recently studied by Galanis, Kandiros, and Kalavasis (SODA'24) where they showed that single-sample learning is possible when roughly $d\leq 2^{k/6.45}$ and impossible when $d\geq (k+1) 2^{k-1}$. Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in $d$, left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of $k$-SAT formulas of bounded degree. Our main contribution is to answer this question negatively. We show that one-shot learning for $k$-SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees $d$ as low as $k^2$ when $\beta$ is sufficiently large, and bootstrap this to small values of $\beta$ when $d$ scales exponentially with $k$, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on $d$ in terms of $\beta$. In particular, for the uniform case $\beta\rightarrow 0$ that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition $d\lesssim 2^{k/2}$. This is nearly optimal (up to constant factors) in the sense that it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for $d\gtrsim 2^{k/2}$.

We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter $\beta>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(\beta_u,\beta_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations. To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all $\beta$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\geq 3$. The only result so far that applies to general $q,d\geq 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for $\beta<\beta_u$. For $\beta>\beta_u$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold $\beta_u$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\geq 3$ beyond the uniqueness threshold $\beta_u$; our analysis works all the way up to the threshold $\beta_c\in (\beta_u,\beta_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime $\beta>\beta_c$ that refines significantly the range of $q,d$., Comment: Abstract shortened to meet arXiv requirements

We present Legal Argument Reasoning (LAR), a novel task designed to evaluate the legal reasoning capabilities of Large Language Models (LLMs). The task requires selecting the correct next statement (from multiple choice options) in a chain of legal arguments from court proceedings, given the facts of the case. We constructed a dataset (LAR-ECHR) for this task using cases from the European Court of Human Rights (ECHR). We evaluated seven general-purpose LLMs on LAR-ECHR and found that (a) the ranking of the models is aligned with that of LegalBench, an established US-based legal reasoning benchmark, even though LAR-ECHR is based on EU law, (b) LAR-ECHR distinguishes top models more clearly, compared to LegalBench, (c) even the best model (GPT-4o) obtains 75.8% accuracy on LAR-ECHR, indicating significant potential for further model improvement. The process followed to construct LAR-ECHR can be replicated with cases from other legal systems., Comment: Published in Natural Legal Language Processing (NLLP) 2024 workshop

In this paper we do three things. First, we outline the conditions under which the interaction rate of inelastic processes that change the internal state of a system of $N$ targets scales as $N^2$. This is an effect distinct from coherent elastic scattering, but with the same scaling. Second, we compute rates for such processes for various weakly interacting particles. Finally, we point to potential quantum observables for these processes, beyond energy exchange. Maximal coherence in inelastic processes is achieved when the targets are placed in an equal superposition of the ground and excited states. These coherent inelastic processes are analogous to Dicke superradiance, and we thus refer to them as superradiant interactions. We compute the superradiant interaction rates for the Cosmic Neutrino Background (C$\nu$B), dark matter scattering and absorption, and late-universe particles, such as reactor neutrinos, when the two-level system is realized by nuclear or electron spins in a magnetic field. The rates can be sizeable on macroscopic yet small targets. For example, the C$\nu$B interacts with a rate of $\mathcal{O}(\text{Hz})$ when scattering off a 10~cm liquid or solid-state density spin-polarized sphere, a $\mathcal{O}(10^{21})$ enhancement compared to the incoherent contribution. For QCD axion dark matter, similar rates can be achieved with much smaller samples, $N \sim \mathcal{O}(10^{15})\left(\frac{m}{2\times 10^{-8}~\text{eV}}\right)^{-1/2}$, where $m$ is the axion mass. Using the Lindblad formalism, we show that these superradiant interactions can manifest as a source of noise on the system. This points to new observables, sensitive to the sum of the excitation and de-excitation rates, and can be viewed as introducing diffusion and decoherence to the system. The effects presented in this paper may point to a new class of ultra-low threshold detectors., Comment: 2 figures added and typos fixed; 19+4 pages, 2 appendices, 10 figures and 5 tables

We consider the problem of sampling from the Ising model when the underlying interaction matrix has eigenvalues lying within an interval of length $\gamma$. Recent work in this setting has shown various algorithmic results that apply roughly when $\gamma< 1$, notably with nearly-linear running times based on the classical Glauber dynamics. However, the optimality of the range of $\gamma$ was not clear since previous inapproximability results developed for the antiferromagnetic case (where the matrix has entries $\leq 0$) apply only for $\gamma>2$. To this end, Kunisky (SODA'24) recently provided evidence that the problem becomes hard already when $\gamma>1$ based on the low-degree hardness for an inference problem on random matrices. Based on this, he conjectured that sampling from the Ising model in the same range of $\gamma$ is NP-hard. Here we confirm this conjecture, complementing in particular the known algorithmic results by showing NP-hardness results for approximately counting and sampling when $\gamma>1$, with strong inapproximability guarantees; we also obtain a more refined hardness result for matrices where only a constant number of entries per row are allowed to be non-zero. The main observation in our reductions is that, for $\gamma>1$, Glauber dynamics mixes slowly when the interactions are all positive (ferromagnetic) for the complete and random regular graphs, due to a bimodality in the underlying distribution. While ferromagnetic interactions typically preclude NP-hardness results, here we work around this by introducing in an appropriate way mild antiferromagnetism, keeping the spectrum roughly within the same range. This allows us to exploit the bimodality of the aforementioned graphs and show the target NP-hardness by adapting suitably previous inapproximability techniques developed for antiferromagnetic systems., Comment: To appear in APPROX/RANDOM 2024

Current- and next-generation gravitational-wave observatories may reveal new, ultralight bosons. Through the superradiance process, these theoretical particle candidates can form clouds around astrophysical black holes and result in detectable gravitational-wave radiation. In the absence of detections, constraints$-$contingent on astrophysical assumptions$-$have been derived using LIGO-Virgo-KAGRA data on boson masses. However, the searches for ultralight scalars to date have not adequately considered self-interactions between particles. Self-interactions that significantly alter superradiance dynamics are generically present for many scalar models, including axion-like dark matter candidates and string axions. We implement the most complete treatment of particle self-interactions available to determine the gravitational-wave signatures expected from superradiant scalar clouds and revisit the constraints obtained in a past gravitational-wave search targeting the black hole in Cygnus X-1. We also project the reach of next-generation gravitational-wave observatories to scalar particle parameter space in the mass-coupling plane. We find that while proposed observatories have insufficient reach to self-interactions that can halt black hole spin-down, next-generation observatories are essential for expanding the search beyond gravitational parameter space and can reach a mass and interaction scale of $\sim 10^{-13}-10^{-12}$ eV/c$^2$ and $\gtrsim 10^{17}$ GeV, respectively.

We study information aggregation in a dynamic trading model with partially informed traders. Ostrovsky [2012] showed that 'separable' securities aggregate information in all equilibria, however, separability is not robust to small changes in the traders' private information. To remedy this problem, we enhance the model by allowing traders to acquire signals with cost $\kappa$, in every period. We show that '$\kappa$ separable securities' aggregate information and, as the cost decreases, nearly all securities become $\kappa$ separable, irrespective of the traders' initial private information. Moreover, the switch to $\kappa$ separability happens not gradually but discontinuously, hence even a small decrease in costs can result in a security aggregating information. Finally, even with myopic traders, cheaper information may accelerate or decelerate information aggregation for all but Arrow-Debreu securities., Comment: 44 pages

The SemEval task on Argument Reasoning in Civil Procedure is challenging in that it requires understanding legal concepts and inferring complex arguments. Currently, most Large Language Models (LLM) excelling in the legal realm are principally purposed for classification tasks, hence their reasoning rationale is subject to contention. The approach we advocate involves using a powerful teacher-LLM (ChatGPT) to extend the training dataset with explanations and generate synthetic data. The resulting data are then leveraged to fine-tune a small student-LLM. Contrary to previous work, our explanations are not directly derived from the teacher's internal knowledge. Instead they are grounded in authentic human analyses, therefore delivering a superior reasoning signal. Additionally, a new `mutation' method generates artificial data instances inspired from existing ones. We are publicly releasing the explanations as an extension to the original dataset, along with the synthetic dataset and the prompts that were used to generate both. Our system ranked 15th in the SemEval competition. It outperforms its own teacher and can produce explanations aligned with the original human analyses, as verified by legal experts., Comment: To be published in SemEval-2024

In the evolving landscape of Federated Learning (FL), a new type of attacks concerns the research community, namely Data Poisoning Attacks, which threaten the model integrity by maliciously altering training data. This paper introduces a novel defensive framework focused on the strategic elimination of adversarial users within a federated model. We detect those anomalies in the aggregation phase of the Federated Algorithm, by integrating metadata gathered by the local training instances with Differential Privacy techniques, to ensure that no data leakage is possible. To our knowledge, this is the first proposal in the field of FL that leverages metadata other than the model's gradients in order to ensure honesty in the reported local models. Our extensive experiments demonstrate the efficacy of our methods, significantly mitigating the risk of data poisoning while maintaining user privacy and model performance. Our findings suggest that this new user elimination approach serves us with a great balance between privacy and utility, thus contributing to the arsenal of arguments in favor of the safe adoption of FL in safe domains, both in academic setting and in the industry., Comment: To be submitted in AISEC 2024

Intensity interferometry is a technique developed many decades ago, that has recently enjoyed a renaissance thanks in part to advances in photodetector technology. We investigate the potential for long-baseline optical intensity interferometry to observe bright, active galactic nuclei (AGN) associated with rapidly accreting supermassive black holes. We argue that realistic telescope arrays similar in area to existing Cherenkov arrays, if equipped with modern high-precision single photon detectors, can achieve a sufficiently high signal to noise ratio not only to detect distant AGN, but also to study them in great detail. We explore the science potential of such observations by considering two examples. First, we find that intensity interferometric observations of bright nearby AGN can allow detailed studies of the central accretion disks powering the AGN, allowing reconstruction of many disk properties like the radial profile. Next, we argue that intensity interferometers can spatially resolve the broad-line regions of AGN at cosmological distances, and thereby provide a geometric determination of the angular diameter distances to those AGN when combined with reverberation mapping. Since this measurement can be performed for AGN at distances of hundreds of megaparsecs, this directly measures the Hubble expansion rate $H_0$, with a precision adequate to resolve the recent Hubble tension. Finally, we speculate on future applications that would be enabled by even larger intensity interferometer arrays.

We consider the problem of estimating the parameters of a Markov Random Field with hard-constraints using a single sample. As our main running examples, we use the $k$-SAT and the proper coloring models, as well as general $H$-coloring models; for all of these we obtain both positive and negative results. In contrast to the soft-constrained case, we show in particular that single-sample estimation is not always possible, and that the existence of an estimator is related to the existence of non-satisfiable instances. Our algorithms are based on the pseudo-likelihood estimator. We show variance bounds for this estimator using coupling techniques inspired, in the case of $k$-SAT, by Moitra's sampling algorithm (JACM, 2019); our positive results for colorings build on this new coupling approach. For $q$-colorings on graphs with maximum degree $d$, we give a linear-time estimator when $q>d+1$, whereas the problem is non-identifiable when $q\leq d+1$. For general $H$-colorings, we show that standard conditions that guarantee sampling, such as Dobrushin's condition, are insufficient for one-sample learning; on the positive side, we provide a general condition that is sufficient to guarantee linear-time learning and obtain applications for proper colorings and permissive models. For the $k$-SAT model on formulas with maximum degree $d$, we provide a linear-time estimator when $k\gtrsim 6.45\log d$, whereas the problem becomes non-identifiable when $k\lesssim \log d$., Comment: Abstract shortened to fit arXiv requirements

We develop in detail a recently proposed optical-path modification of astronomical intensity interferometers. Extended-Path Intensity Correlation (EPIC) introduces a tunable path extension, enabling differential astrometry of multiple compact sources such as stars and quasars at separations of up to a few arcseconds. Combined with other recent technological advances in spectroscopy and fast single-photon detection, a ground-based intensity interferometer array can achieve microarcsecond resolution and even better light-centroiding accuracy on bright sources of magnitude $m \lesssim 15$. We lay out the theory and technical requirements of EPIC, and discuss the scientific potential. Promising applications include astrometric lensing of stars and quasar images, binary-orbit characterization, exoplanet detection, Galactic acceleration measurements and calibration of the cosmic distance ladder. The introduction of the path extension thus significantly increases the scope of intensity interferometry while reaching unprecedented levels of relative astrometric precision., Comment: 58+21 pages, 22 figures; companion paper to arXiv:2307.03221

Intensity interferometry -- the correlation of spatially separated light intensities -- has historically been an important tool for precision optical astronomical observations. However, due to the extremely narrow field of view, its scope has been limited to studies of the morphology of very bright emission regions, primarily determinations of angular diameters of nearby hot stars. We propose adding an adjustable path extension into the detector optics which creates a primary interference fringe for widely separated sources, allowing maximum source separations parametrically larger than the angular resolution. This Extended-Path Intensity Correlator (EPIC), augmented with advances in single-photon detectors and spectroscopic gratings, would enable ground-based astrometry at microarcsecond-level precision in a field of view as large as several arcseconds. EPIC has the potential to revolutionize astrophysical and cosmological observations requiring high-precision differential astrometry on sources of high surface brightness. We outline how EPIC can be employed to detect the astrometric wobble of Earth-like planets around Sun-like stars at tens to hundreds of parsecs, and expect that EPIC's larger field of view will expand the power of intensity interferometry to a broad range of astronomical applications., Comment: 5+3 pages, 3 figures

We consider the performance of Glauber dynamics for the random cluster model with real parameter $q>1$ and temperature $\beta>0$. Recent work by Helmuth, Jenssen and Perkins detailed the ordered/disordered transition of the model on random $\Delta$-regular graphs for all sufficiently large $q$ and obtained an efficient sampling algorithm for all temperatures $\beta$ using cluster expansion methods. Despite this major progress, the performance of natural Markov chains, including Glauber dynamics, is not yet well understood on the random regular graph, partly because of the non-local nature of the model (especially at low temperatures) and partly because of severe bottleneck phenomena that emerge in a window around the ordered/disordered transition. Nevertheless, it is widely conjectured that the bottleneck phenomena that impede mixing from worst-case starting configurations can be avoided by initialising the chain more judiciously. Our main result establishes this conjecture for all sufficiently large $q$ (with respect to $\Delta$). Specifically, we consider the mixing time of Glauber dynamics initialised from the two extreme configurations, the all-in and all-out, and obtain a pair of fast mixing bounds which cover all temperatures $\beta$, including in particular the bottleneck window. Our result is inspired by the recent approach of Gheissari and Sinclair for the Ising model who obtained a similar-flavoured mixing-time bound on the random regular graph for sufficiently low temperatures. To cover all temperatures in the RC model, we refine appropriately the structural results of Helmuth, Jenssen and Perkins about the ordered/disordered transition and show spatial mixing properties "within the phase", which are then related to the evolution of the chain.

We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random $k$-SAT model when the density of the formula scales exponentially with $k$. The best previously known sampling algorithm for the random $k$-SAT model applies when the density $\alpha=m/n$ of the formula is less than $2^{k/300}$ and runs in time $n^{\exp(\Theta(k))}$. Here $n$ is the number of variables and $m$ is the number of clauses. Our algorithm achieves a significantly faster running time of $n^{1 + o_k(1)}$ and samples satisfying assignments up to density $\alpha\leq 2^{0.039 k}$. The main challenge in our setting is the presence of many variables with unbounded degree, which causes significant correlations within the formula and impedes the application of relevant Markov chain methods from the bounded-degree setting. Our main technical contribution is a $o_k(\log n )$ bound of the sum of influences in the $k$-SAT model which turns out to be robust against the presence of high-degree variables. This allows us to apply the spectral independence framework and obtain fast mixing results of a uniform-block Glauber dynamics on a carefully selected subset of the variables. The final key ingredient in our method is to take advantage of the sparsity of logarithmic-sized connected sets and the expansion properties of the random formula, and establish relevant connectivity properties of the set of satisfying assignments that enable the fast simulation of this Glauber dynamics. Our results also allow us to conclude that, with high probability, a random $k$-CNF formula with density at most $2^{0.227 k}$ has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance $O_k(\log n)$. We are also able to deduce looseness results for random $k$-CNFs in the same regime., Comment: This is a merger with the independent work arxiv:2207.02841. To appear in SIDMA

We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph. In a recent work, we established NP-hardness of approximating the average size of an independent set utilizing hardness of the corresponding optimization problem and the related phase transition behavior. Here, we instead consider settings where the underlying optimization problem is easily solvable. Our main contribution is to classify the complexity of approximating a wide class of observables via a generic reduction from approximate counting to the problem of estimating local observables. The key idea is to use the observables to interpolate the counting problem. Using this new approach, we are able to study observables on bipartite graphs where the underlying optimization problem is easy but the counting problem is believed to be hard. The most-well studied class of graphs that was excluded from previous hardness results were bipartite graphs. We establish hardness for estimating the average size of the independent set in bipartite graphs of maximum degree 6; more generally, we show tight hardness results for general vertex-edge observables for antiferromagnetic 2-spin systems on bipartite graphs. Our techniques go beyond 2-spin systems, and for the ferromagnetic Potts model we establish hardness of approximating the number of monochromatic edges in the same region as known hardness of approximate counting results.

Exploring dark matter via observations of extreme astrophysical environments -- defined here as heavy compact objects such as white dwarfs, neutron stars, and black holes, as well as supernovae and compact object merger events -- has been a major field of growth since the last Snowmass process. Theoretical work has highlighted the utility of current and near-future observatories to constrain novel dark matter parameter space across the full mass range. This includes gravitational wave instruments and observatories spanning the electromagnetic spectrum, from radio to gamma-rays. While recent searches already provide leading sensitivity to various dark matter models, this work also highlights the need for theoretical astrophysics research to better constrain the properties of these extreme astrophysical systems. The unique potential of these search signatures to probe dark matter adds motivation to proposed next-generation astronomical and gravitational wave instruments., Comment: Contribution to Snowmass 2021 -- CF3. Dark Matter: Cosmic Probes

We study the performance of Markov chains for the $q$-state ferromagnetic Potts model on random regular graphs. It is conjectured that their performance is dictated by metastability phenomena, i.e., the presence of "phases" (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the metastable phases for the $q$-state Potts model on the $d$-regular random graph for all integers $q,d\geq 3$, and establish that for an interval of temperatures, which is delineated by the uniqueness and a broadcasting threshold on the $d$-regular tree, the two phases coexist. The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. Based on this new structural understanding of the model, we obtain various algorithmic consequences. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph "planting" argument combined with delicate bounds on random-graph percolation., Comment: Abstract shortened for arXiv. To appear in Communications in Mathematical Physics (CIMP)

It is well-known that stars have the potential to be excellent dark matter detectors. Infalling dark matter that scatters within stars could lead to a range of observational signatures, including stellar heating, black hole formation, and modified heat transport. To make robust predictions for such phenomena, it is necessary to calculate the scattering rate for dark matter inside the star. As we show in this paper, for small enough momentum transfers, this requires taking into account collective effects within the dense stellar medium. These effects have been neglected in many previous treatments; we demonstrate how to incorporate them systematically, and show that they can parametrically enhance or suppress dark matter scattering rates depending on how dark matter couples to the Standard Model. We show that, as a result, collective effects can significantly modify the potential discovery or exclusion reach for observations of compact objects such as white dwarfs and neutron stars. While the effects are more pronounced for dark matter coupling through a light mediator, we show that even for dark matter coupling via a heavy mediator, scattering rates can differ by orders of magnitude from their naive values for dark matter masses <~ 100 MeV. We also illustrate how collective effects can be important for dark matter scattering in more dilute media, such as the Solar core. Our results demonstrate the need to systematically incorporate collective effects in a wide range of astroparticle contexts; to facilitate this, we provide expressions for in-medium self-energies for a variety of different media, which are applicable to many other processes of interest (such as particle production)., Comment: 66 pages, 14 figures; v3, matches version published in JCAP

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal $O(n \log n)$ sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using $L^p$-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of $L^p$-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the $L^p$-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph $G(n,d/n)$, where the previously known algorithms run in time $n^{O(\log d)}$ or applied only to large $d$. We refine these algorithmic bounds significantly, and develop fast $n^{1+o(1)}$ algorithms based on Glauber dynamics that apply to all $d$, throughout the uniqueness regime., Comment: TALG, To Appear

One contribution to any dark sector's abundance comes from its gravitational production during inflation. If the dark sector is weakly coupled to the inflaton and the Standard Model, this can be its only production mechanism. For non-interacting dark sectors, such as a free massive fermion or a free massive vector field, this mechanism has been studied extensively. In this paper we show, via the example of dark massive QED, that the presence of interactions can result in a vastly different mass for the dark matter (DM) particle, which may well coincide with the range probed by upcoming experiments. In the context of dark QED we study the evolution of the energy density in the dark sector after inflation. Inflation produces a cold vector condensate consisting of an enormous number of bosons, which via interesting processes - Schwinger pair production, strong field electromagnetic cascades, and plasma dynamics - transfers its energy to a small number of "dark electrons" and triggers thermalization of the dark sector. The resulting dark electron DM mass range is from 50 MeV to 30 TeV, far different from both the $10^{-5}$ eV mass of the massive photon dark matter in the absence of dark electrons, and from the $10^9$ GeV dark electron mass in the absence of dark photons. This can significantly impact the search strategies for dark QED and, more generally, theories with a self-interacting DM sector. In the presence of kinetic mixing, a dark electron in this mass range can be searched for with upcoming direct detection experiments, such as SENSEI-100g and OSCURA., Comment: 33+51 pages, 19 figures; v2: references added, expanded App. B

Recent developments in approximate counting have made startling progress in developing fast algorithmic methods for approximating the number of solutions to constraint satisfaction problems (CSPs) with large arities, using connections to the Lovasz Local Lemma. Nevertheless, the boundaries of these methods for CSPs with non-Boolean domain are not well-understood. Our goal in this paper is to fill in this gap and obtain strong inapproximability results by studying the prototypical problem in this class of CSPs, hypergraph colourings. More precisely, we focus on the problem of approximately counting $q$-colourings on $K$-uniform hypergraphs with bounded degree $\Delta$. An efficient algorithm exists if $\Delta\lesssim \frac{q^{K/3-1}}{4^KK^2}$ (Jain, Pham, and Vuong, 2021; He, Sun, and Wu, 2021). Somewhat surprisingly however, a hardness bound is not known even for the easier problem of finding colourings. For the counting problem, the situation is even less clear and there is no evidence of the right constant controlling the growth of the exponent in terms of $K$. To this end, we first establish that for general $q$ computational hardness for finding a colouring on simple/linear hypergraphs occurs at $\Delta\gtrsim Kq^K$, almost matching the algorithm from the Lovasz Local Lemma. Our second and main contribution is to obtain a far more refined bound for the counting problem that goes well beyond the hardness of finding a colouring and which we conjecture that is asymptotically tight (up to constant factors). We show in particular that for all even $q\geq 4$ it is NP-hard to approximate the number of colourings when $\Delta\gtrsim q^{K/2}$., Comment: abstract shortened for arXiv

For spin systems, such as the $q$-colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-range correlations, is typically computationally hard for bounded-degree graphs. We present new algorithmic results for approximating the partition function and sampling from the Gibbs distribution for spin systems in the non-uniqueness region on random regular bipartite graphs. We give an $\mathsf{FPRAS}$ for counting $q$-colorings for even $q=O\big(\tfrac{\Delta}{\log{\Delta}}\big)$ on almost every $\Delta$-regular bipartite graph. This is within a factor $O(\log{\Delta})$ of the sampling algorithm for general graphs in the uniqueness region and improves significantly upon the previous best bound of $q=O\big(\tfrac{\sqrt{\Delta}}{(\log\Delta)^2}\big)$ by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independent sets weighted by $\lambda>0$, we present an $\mathsf{FPRAS}$ for estimating the partition function when $\lambda=\Omega\big(\tfrac{\log{\Delta}}{\Delta}\big)$, which improves upon previous results by an $\Omega(\log \Delta)$ factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our result for colorings is within a constant factor of best possible using current polymer-method approaches.

The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework. We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems.

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs~$G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i,-i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert > 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model., Comment: 49 pages, 9 figures On last update: we fixed some typos and updated the references

Natural Language Processing (NLP) has evolved significantly over the last decade. This paper highlights the most important milestones of this period while trying to pinpoint the contribution of each individual model and algorithm to the overall progress. Furthermore, it focuses on issues still remaining to be solved, emphasizing the groundbreaking proposals of Transformers, BERT, and all the similar attention-based models., Comment: 13 pages, 5 figures

Black hole superradiance is a powerful probe of light, weakly-coupled hidden sector particles. Many candidate particles, such as axions, generically have self-interactions that can influence the evolution of the superradiant instability. As pointed out in arXiv:1604.06422 in the context of a toy model, much of the existing literature on spin-0 superradiance does not take into account the most important self-interaction-induced processes. These processes lead to energy exchange between quasi-bound levels and particle emission to infinity; for large self-couplings, superradiant growth is saturated at a quasi-equilibrium configuration of reduced level occupation numbers. In this paper, we perform a detailed analysis of the rich dynamics of spin-0 superradiance with self-interactions, and the resulting observational signatures. We focus on quartic self-interactions, which dominate the evolution for most models of interest. We explore multiple distinct regimes of parameter space introduced by a non-zero self-interaction, including the simultaneous population of two or more bound levels; at large coupling, we confirm the basic picture of quasi-equilibrium saturation and provide evidence that the "bosenova" collapse does not occur in most of the astrophysical parameter space. Compared to gravitational superradiance, we find that gravitational wave "annihilation" signals and black hole spin-down are parametrically suppressed with increasing interactions, while new gravitational wave "transition" signals can take place for moderate interactions. The novel phenomenon of scalar wave emission is less suppressed at large couplings, and if the particle has Standard Model interactions, then coherent, monochromatic axion wave signals from black hole superradiance may be detectable in proposed axion dark matter experiments., Comment: 60 pages, 30 figures; v2: figures and comments added to Sec. VIII. Minor changes to Sec. VII

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let $\alpha^*\approx 1.763$ denote the solution to $\exp(1/x)=x$ and let $\alpha>\alpha^*$. We prove that, for any triangle-free graph $G=(V,E)$ with maximum degree $\Delta$, for all $q\geq\alpha\Delta+1$, the mixing time of the Glauber dynamics for $q$-colorings is polynomial in $n=|V|$, with the exponent of the polynomial independent of $\Delta$ and $q$. In comparison, previous approximate counting results for colorings held for a similar range of $q$ (asymptotically in $\Delta$) but with larger girth requirement or with a running time where the polynomial exponent depended on $\Delta$ and $q$ (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $\lambda$ on the unit circle in the complex plane. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all $|\lambda|\neq 1$ by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens around $\lambda=1$, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point $\lambda=1$, and more generally on the entire unit circle. For an integer $\Delta\geq 3$ and edge interaction parameter $b\in (0,1)$ we show #P-hardness for approximating the partition function on graphs of maximum degree $\Delta$ on the arc of the unit circle where the Lee-Yang zeros are dense. This result contrasts with known approximation algorithms when $|\lambda|\neq 1$ or when $\lambda$ is in the complementary arc around $1$ of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs., Comment: 40 pages, 1 figure. We have included a new result for the case $b\in [1-2/\Delta,1)$. This essentially gives a complete picture of the complexity of the problem. An extended abstract has been presented at SODA 2021

We study the complexity of approximating the partition function of the $q$-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on $q=2$, which corresponds to the case of the Ising model; for $q>2$, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing \#P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all $q\geq 2$ and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lov\'{a}sz and Welsh in the context of quantum computations., Comment: 58 pages. Changes on version 2: minor changes

A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander $\Delta$-regular graphs, including the canonical class of bipartite random $\Delta$-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Our approach generalises the techniques of Jenseen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to "bicliques" of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in $\tilde{O}(n^2)$ time, where $n$ is the size of the graph.

We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum degree 6. This is a special case of a more general result for the hard-core model defined on independent sets weighted by a parameter $\lambda>0$. In the general setting, we prove that, unless P=NP, for all $\Delta\geq 3$, all $\lambda>\lambda_c(\Delta)$, there is no FPTAS which applies to all graphs of maximum degree $\Delta$ for computing the average size of the independent set in the Gibbs distribution, where $\lambda_c(\Delta)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $\Delta$-regular tree. Moreover, we prove that for $\lambda$ in a dense set of this non-uniqueness region the problem is NP-hard to approximate within some constant factor. Our work extends to the antiferromagnetic Ising model and generalizes to all 2-spin antiferromagnetic models, establishing hardness of computing the average magnetization in the tree non-uniqueness region. Previously, Schulman, Sinclair and Srivastava (2015) showed that it is #P-hard to compute the average magnetization exactly, but no hardness of approximation results were known. Hardness results of Sly (2010) and Sly and Sun (2014) for approximating the partition function do not imply hardness of computing averages. The new ingredient in our reduction is an intricate construction of pairs of rooted trees whose marginal distributions at the root agree but their derivatives disagree. The main technical contribution is controlling what marginal distributions and derivatives are achievable and using Cauchy's functional equation to argue existence of the gadgets., Comment: Minor update to make "field gadgets" bipartite (Lemma 30)

With regard to the wider area of AI/LT platform interoperability, we concentrate on two core aspects: (1) cross-platform search and discovery of resources and services; (2) composition of cross-platform service workflows. We devise five different levels (of increasing complexity) of platform interoperability that we suggest to implement in a wider federation of AI/LT platforms. We illustrate the approach using the five emerging AI/LT platforms AI4EU, ELG, Lynx, QURATOR and SPEAKER., Comment: Proceedings of the 1st International Workshop on Language Technology Platforms (IWLTP 2020). To appear