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)