Explore the vast range of titles available.

#SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and computing the volume of a polytope. In the realm of satisfiability modulo theories (SMT) there is a growing need for model counting solvers, coming from several application domains (quantitative information flow, static analysis of probabilistic programs). In this paper, we show a reduction from an approximate version of #SMT  to SMT. We focus on the theories of integer arithmetic and linear real arithmetic. We propose model counting algorithms that provide approximate solutions with formal bounds on the approximation error. They run in polynomial time and make a polynomial number of queries to the SMT solver for the underlying theory, exploiting “for free” the sophisticated heuristics implemented within modern SMT solvers. We have implemented the algorithms and used them to solve the value problem for a model of loop-free probabilistic programs with nondeterminism.

We consider versions of the grasshopper problem (Goulko & Kent 2017 Proc. R. Soc. A 473 , 20170494) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference 2 π , we show that for unconstrained lawns of any length and arbitrary jump lengths, the supremum of the probability for the grasshopper’s jump to stay on the lawn is one. For antipodal lawns, which by definition contain precisely one of each pair of opposite points and have length π , we show this is true except when the jump length ϕ is of the form π ( p / q ) with p , q coprime and p odd. For these jump lengths, we show the optimal probability is 1 − 1/ q and construct optimal lawns. For a pair of antipodal lawns, we show that the optimal probability of jumping from one onto the other is 1 − 1/ q for p , q coprime, p odd and q even, and one in all other cases. For an antipodal lawn on the sphere, it is known (Kent & Pitalúa-García 2014 Phys. Rev. A 90 , 062124) that if ϕ  =  π / q , where q ∈ N , then the optimal retention probability of 1 − 1/ q for the grasshopper’s jump is provided by a hemispherical lawn. We show that in all other cases where 0 <  ϕ  <  π /2, hemispherical lawns are not optimal, disproving the hemispherical colouring maximality hypotheses (Kent & Pitalúa-García 2014 Phys. Rev. A 90 , 062124). We discuss the implications for Bell experiments and related cryptographic tests.

We consider versions of the grasshopper problem (Goulko & Kent 2017 Proc. R. Soc. A 473, 20170494) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference 2π, we show that for unconstrained lawns of any length and arbitrary jump lengths, the supremum of the probability for the grasshopper’s jump to stay on the lawn is one. For antipodal lawns, which by definition contain precisely one of each pair of opposite points and have length π, we show this is true except when the jump length ϕ is of the form π(p/q) with p, q coprime and p odd. For these jump lengths, we show the optimal probability is 1 − 1/q and construct optimal lawns. For a pair of antipodal lawns, we show that the optimal probability of jumping from one onto the other is 1 − 1/q for p, q coprime, p odd and q even, and one in all other cases. For an antipodal lawn on the sphere, it is known (Kent & Pitalúa-García 2014 Phys. Rev. A 90, 062124) that if ϕ = π/q, where q ∈ ℕ, then the optimal retention probability of 1 − 1/q for the grasshopper’s jump is provided by a hemispherical lawn. We show that in all other cases where 0 < ϕ < π/2, hemispherical lawns are not optimal, disproving the hemispherical colouring maximality hypotheses (Kent & Pitalúa-García 2014 Phys. Rev. A 90, 062124). We discuss the implications for Bell experiments and related cryptographic tests.

This paper provides an NP procedure that decides whether a linear-exponential system of constraints has an integer solution. Linear-exponential systems extend standard integer linear programs with exponential terms \\(2^x\\) and remainder terms \\({(x \\bmod 2^y)}\\). Our result implies that the existential theory of the structure \\((\\mathbb{N},0,1,+,2^{(\\cdot)},V_2(\\cdot,\\cdot),\\leq)\\) has an NP-complete satisfiability problem, thus improving upon a recent EXPSPACE upper bound. This theory extends the existential fragment of Presburger arithmetic with the exponentiation function \\(x \\mapsto 2^x\\) and the binary predicate \\(V_2(x,y)\\) that is true whenever \\(y \\geq 1\\) is the largest power of \\(2\\) dividing \\(x\\). Our procedure for solving linear-exponential systems uses the method of quantifier elimination. As a by-product, we modify the classical Gaussian variable elimination into a non-deterministic polynomial-time procedure for integer linear programming (or: existential Presburger arithmetic).

Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is big-O of another, the problem of finding or approximating the associated constant is also undecidable. Our positive results show that the big-O problem is polynomial-time solvable for unambiguous automata, coNP-complete for unlabelled weighted automata (i.e., when the alphabet is a single character) and decidable, subject to Schanuel's conjecture, when the language is bounded (i.e., a subset of \\(w_1^* w_m^*\\) for some finite words \\(w_1, w_m\\)) or when the automaton has finite ambiguity. On labelled Markov chains, the problem can be restated as a ratio total variation distance, which, instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem is related to \\(\\)-differential privacy, for which the optimal constant of the big-O notation is exactly \\(()\\).

The spherical grasshopper problem is a geometric optimization problem that arises in the context of Bell inequalities and can be interpreted as identifying the best local hidden variable approximation to quantum singlet correlations for measurements along random axes separated by a fixed angle. In a parallel publication [arXiv:2504.20953], we presented numerical solutions for this problem and explained their significance for singlet simulation and testing. In this companion paper, we describe in detail the geometric and computational framework underlying these results. We examine the role of spherical discretization and compare three natural variants of the problem: antipodal complementary lawns, antipodal independent lawns, and non-antipodal complementary lawns. We analyze the geometric structure of the corresponding optimal lawn configurations and interpret it in terms of a spherical harmonics expansion. We also discuss connections to other physical models and to classical problems in geometric probability.

We prove that, for the fundamental regression task of learning a single neuron, training a one-hidden layer ReLU network of any width by gradient flow from a small initialisation converges to zero loss and is implicitly biased to minimise the rank of network parameters. By assuming that the training points are correlated with the teacher neuron, we complement previous work that considered orthogonal datasets. Our results are based on a detailed non-asymptotic analysis of the dynamics of each hidden neuron throughout the training. We also show and characterise a surprising distinction in this setting between interpolator networks of minimal rank and those of minimal Euclidean norm. Finally we perform a range of numerical experiments, which corroborate our theoretical findings.

Bell's seminal work showed that no local hidden variable (LHV) model can fully reproduce the quantum correlations of a two-qubit singlet state. His argument and later developments by Clauser et al. effectively rely on gaps between the anticorrelations achievable by classical models and quantum theory for projective measurements along randomly chosen axes separated by a fixed angle. However, the size of these gaps has to date remained unknown. Here we numerically determine the LHV models maximizing anticorrelations for random axes separated by any fixed angle, by mapping the problem onto ground state configurations of fixed-range spin models. We identify angles where this gap is largest and thus best suited for Bell tests. These findings enrich the understanding of Bell non-locality as a physical resource in quantum information theory and quantum cryptography.

We investigate expansions of Presburger arithmetic, i.e., the theory of the integers with addition and order, with additional structure related to exponentiation: either a function that takes a number to the power of \\(2\\), or a predicate for the powers of \\(2\\). The latter theory, denoted \\(\\mathrm{PresPower}\\), was introduced by B\"uchi as a first attempt at characterising the sets of tuples of numbers that can be expressed using finite automata; B\"uchi's method does not give an elementary upper bound, and the complexity of this theory has been open. The former theory, denoted as \\(\\mathrm{PresExp}\\), was shown decidable by Semenov; while the decision procedure for this theory differs radically from the automata-based method proposed by B\"uchi, the method is also non-elementary. And in fact, the theory with the power function has a non-elementary lower bound. In this paper, we show that while Semenov's and B\"uchi's approaches yield non-elementary blow-ups for \\(\\mathrm{PresPower}\\), the theory is in fact decidable in triply exponential time, similar to the best known quantifier-elimination algorithm for Presburger arithmetic. We also provide a \\(\\mathrm{NExpTime}\\) upper bound for the existential fragment of \\(\\mathrm{PresExp}\\), a step towards a finer-grained analysis of its complexity. Both these results are established by analysing a single parameterized satisfiability algorithm for \\(\\mathrm{PresExp}\\), which can be specialized to either the setting of \\(\\mathrm{PresPower}\\) or the existential theory of \\(\\mathrm{PresExp}\\). Besides the new upper bounds for the existential theory of \\(\\mathrm{PresExp}\\) and \\(\\mathrm{PresPower}\\), we believe our algorithm provides new intuition for the decidability of these theories, and for the features that lead to non-elementary blow-ups.

We study the reachability problem for one-counter automata in which transitions can carry disequality tests. A disequality test is a guard that prohibits a specified counter value. This reachability problem has been known to be NP-hard and in PSPACE, and characterising its computational complexity has been left as a challenging open question by Almagor, Cohen, Pérez, Shirmohammadi, and Worrell (2020). We reduce the complexity gap, placing the problem into the second level of the polynomial hierarchy, namely into the class \\(\\mathsf{coNP}^{\\mathsf{NP}}\\). In the presence of both equality and disequality tests, our upper bound is at the third level, \\(\\mathsf{P}^{\\mathsf{NP}^{\\mathsf{NP}}}\\). To prove this result, we show that non-reachability can be witnessed by a pair of invariants (forward and backward). These invariants are almost inductive. They aim to over-approximate only a \"core\" of the reachability set instead of the entire set. The invariants are also leaky: it is possible to escape the set. We complement this with separate checks as the leaks can only occur in a controlled way.