2025-07-18 | | Total: 188
Frontier AI models demonstrate formidable breadth of knowledge. But how close are they to true human -- or superhuman -- expertise? Genuine experts can tackle the hardest problems and push the boundaries of scientific understanding. To illuminate the limits of frontier model capabilities, we turn away from contrived competitive programming puzzles, and instead focus on real-life research problems. We construct FormulaOne, a benchmark that lies at the intersection of graph theory, logic, and algorithms, all well within the training distribution of frontier models. Our problems are incredibly demanding, requiring an array of reasoning steps. The dataset has three key properties. First, it is of commercial interest and relates to practical large-scale optimisation problems, such as those arising in routing, scheduling, and network design. Second, it is generated from the highly expressive framework of Monadic Second-Order (MSO) logic on graphs, paving the way toward automatic problem generation at scale; ideal for building RL environments. Third, many of our problems are intimately related to the frontier of theoretical computer science, and to central conjectures therein, such as the Strong Exponential Time Hypothesis (SETH). As such, any significant algorithmic progress on our dataset, beyond known results, could carry profound theoretical implications. Remarkably, state-of-the-art models like OpenAI's o3 fail entirely on FormulaOne, solving less than 1% of the questions, even when given 10 attempts and explanatory fewshot examples -- highlighting how far they remain from expert-level understanding in some domains. To support further research, we additionally curate FormulaOne-Warmup, offering a set of simpler tasks, from the same distribution. We release the full corpus along with a comprehensive evaluation framework.
We study the Finite-Dimensional Distributions (FDDs) of deep neural networks with randomly initialized weights that have finite-order moments. Specifically, we establish Gaussian approximation bounds in the Wasserstein-$1$ norm between the FDDs and their Gaussian limit assuming a Lipschitz activation function and allowing the layer widths to grow to infinity at arbitrary relative rates. In the special case where all widths are proportional to a common scale parameter $n$ and there are $L-1$ hidden layers, we obtain convergence rates of order $n^{-({1}/{6})^{L-1} + \epsilon}$, for any $\epsilon > 0$.
Physics-Informed Neural Networks (PINNs) are deep learning models that incorporate the governing physical laws of a system into the learning process, making them well-suited for solving complex scientific and engineering problems. Recently, PINNs have gained widespread attention as a powerful framework for combining physical principles with data-driven modeling to improve prediction accuracy. Despite their successes, however, PINNs often exhibit poor extrapolation performance outside the training domain and are highly sensitive to the choice of activation functions (AFs). In this paper, we introduce a transfer learning (TL) method to improve the extrapolation capability of PINNs. Our approach applies transfer learning (TL) within an extended training domain, using only a small number of carefully selected collocation points. Additionally, we propose an adaptive AF that takes the form of a linear combination of standard AFs, which improves both the robustness and accuracy of the model. Through a series of experiments, we demonstrate that our method achieves an average of 40% reduction in relative L2 error and an average of 50% reduction in mean absolute error in the extrapolation domain, all without a significant increase in computational cost. The code is available at https://github.com/LiuzLab/PINN-extrapolation .
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing its structure and label set. We consider classes where permutations move only finitely many vertices. Our main result shows that PAC learnability of all such finite-support copies implies online learnability of the full isomorphism type of G, and is equivalent to the condition of automorphic triviality. We also characterize graphs where copies induced by swapping two vertices are not learnable, using a relaxation of the extension property of the infinite random graph. Finally, we show that, for all G and k>2, learnability for k-vertex permutations is equivalent to that for 2-vertex permutations, yielding a four-class partition of infinite graphs, whose complexity we also determine using tools coming from both descriptive set theory and computability theory.
The combination of higher-order theories and fuzzy logic can be useful in decision-making tasks that involve reasoning across abstract functions and predicates, where exact matches are often rare or unnecessary. Developing efficient reasoning and computational techniques for such a combined formalism presents a significant challenge. In this paper, we adopt a more straightforward approach aiming at integrating two well-established and computationally well-behaved components: higher-order patterns on one side and fuzzy equivalences expressed through similarity relations based on minimum T-norm on the other. We propose a unification algorithm for higher-order patterns modulo these similarity relations and prove its termination, soundness, and completeness. This unification problem, like its crisp counterpart, is unitary. The algorithm computes a most general unifier with the highest degree of approximation when the given terms are unifiable.
The present work revisits and provides a new approach on a result by Charles Ballantine, on the factorization of a square matrix with positive determinant into a product of positive definite factors. {\em Ballantine-type} factorizations, that bound the number of positive definite factors, proved central in solving a basic, yet elusive control problem--the strong controllability of a linear system via control in the form of state feedback. Ballantine's result transcends control engineering, and highlights the little appreciated fact that rotations can be realized by the successive application of irrotational motions. Our approach is constructive and is based on the theory of optimal mass transport, specifically, it relates successive rotations of Gaussian distributions to corresponding optimal transport maps that constitute the sought factors.
Modeling how information travels throughout a network has vast applications across social sciences, cybersecurity, and graph-based neural networks. In this paper, we consider the zero forcing model for information diffusion on iterative deterministic complex network models. In particular, we continue the exploration of the Iterative Local Transitive (ILT) model and the Iterative Local Anti-Transitive (ILAT) model, both introduced by Bonato et. al. in 2009 and 2017, respectively. These models use ideas from Structural Balance Theory to generate edges through a notion of cloning where ``the friend of my friend is my friend'' and anticloning where ``the enemy of my enemy is my friend.'' Zero forcing, introduced independently by Burgarth and Giovanetti and a special working group at AIM in 2007 and 2008, begins with some set of forced vertices, the remaining are unforced. If a forced vertex has a single unforced neighbor, that neighbor becomes forced. The minimum number of vertices in a starting set required to guarantee all vertices eventually become forced is the zero forcing number of the graph. The maximum number of vertices in a starting set such that the graph cannot become fully forced is the failed zero forcing number of a graph. In this paper we provide bounds for both the zero forcing and failed zero forcing number of graphs created using both the ILT and ILAT models. In particular, we show that in the case of ILAT graphs the failed zero forcing number can only take on one of four values, dependent on the number of vertices of the graph. Finally, we briefly consider another information diffusion model, graph burning, on a more general iterated graph model.
This paper explores local second-order weak sharp minima for a broad class of nonconvex optimization problems. We propose novel second-order optimality conditions formulated through the use of classical and lower generalized support functions. These results are based on asymptotic second-order tangent cones and outer second-order tangent sets. Specifically, our findings eliminate the necessity of assuming convexity in the constraint set and/or the outer second-order tangent set, or the nonemptiness of the outer second-order tangent set. Furthermore, unlike traditional approaches, our sufficient conditions do not rely on strong assumptions such as the uniform second-order regularity of the constraint set and the property of uniform approximation of the critical cones.
Data classification without access to labeled samples remains a challenging problem. It usually depends on an appropriately chosen distance between features, a topic addressed in metric learning. Recently, Huizing, Cantini and Peyré proposed to simultaneously learn optimal transport (OT) cost matrices between samples and features of the dataset. This leads to the task of finding positive eigenvectors of a certain nonlinear function that maps cost matrices to OT distances. Having this basic idea in mind, we consider both the algorithmic and the modeling part of unsupervised metric learning. First, we examine appropriate algorithms and their convergence. In particular, we propose to use the stochastic random function iteration algorithm and prove that it converges linearly for our setting, although our operators are not paracontractive as it was required for convergence so far. Second, we ask the natural question if the OT distance can be replaced by other distances. We show how Mahalanobis-like distances fit into our considerations. Further, we examine an approach via graph Laplacians. In contrast to the previous settings, we have just to deal with linear functions in the wanted matrices here, so that simple algorithms from linear algebra can be applied.
An increasing number of studies have focused on stochastic first-order methods (SFOMs) under heavy-tailed gradient noises, which have been observed in the training of practical deep learning models. In this paper, we focus on two types of gradient noises: one is sub-Weibull noise, and the other is noise under the assumption that it has a bounded $p$-th central moment ($p$-BCM) with $p\in (1, 2]$. The latter is more challenging due to the occurrence of infinite variance when $p\in (1, 2)$. Under these two gradient noise assumptions, the in-expectation and high-probability convergence of SFOMs have been extensively studied in the contexts of convex optimization and standard smooth optimization. However, for weakly convex objectives-a class that includes all Lipschitz-continuous convex objectives and smooth objectives-our understanding of the in-expectation and high-probability convergence of SFOMs under these two types of noises remains incomplete. We investigate the high-probability convergence of the vanilla stochastic subgradient descent (SsGD) method under sub-Weibull noises, as well as the high-probability and in-expectation convergence of clipped SsGD under the $p$-BCM noises. Both analyses are conducted in the context of weakly convex optimization. For weakly convex objectives that may be non-convex and non-smooth, our results demonstrate that the theoretical dependence of vanilla SsGD on the failure probability and number of iterations under sub-Weibull noises does not degrade compared to the case of smooth objectives. Under $p$-BCM noises, our findings indicate that the non-smoothness and non-convexity of weakly convex objectives do not impact the theoretical dependence of clipped SGD on the failure probability relative to the smooth case; however, the sample complexity we derived is worse than a well-known lower bound for smooth optimization.
Graphical designs are subsets of vertices of a graph that perfectly average a selected set of eigenvectors of the Graph Laplacian. We show that in highly-structured graphs, graphical designs can coincide with highly structured and well-known combinatorial objects: orthogonal arrays in hypercube graphs, combinatorial block designs and extremizers of the Erdos-Ko-Rado theorem in Johnson graphs, and t-wise uniform sets of permutations and symmetric subgroups in normal Cayley graphs on the symmetric group. These connections allow tools from spectral graph theory to bear on these combinatorial objects. We also show that the central vertex in a Mycielskian is an extremely good design and certain designs of the Mycielskian coincide with designs of the original graph.
The St. Petersburg paradox presents a longstanding challenge in decision theory. It describes a game whose expected value is infinite, yet for which no rational finite stake can be determined. Traditional solutions introduce auxiliary assumptions, such as diminishing marginal utility, temporal discounting, or extended number systems. These methods often involve mathematical refinements that may not correspond to how people actually perceive or process numerical information. This paper explores an alternative approach based on a modified operation of addition defined over coarse partitions of the outcome space. In this model, exact numerical values are grouped into perceptual categories, and each value is replaced by a representative element of its group before being added. This method allows for a phenomenon where repeated additions eventually cease to affect the outcome, a behavior described as inertial stabilization. Although this is not intended as a definitive resolution of the paradox, the proposed framework offers a plausible way to represent how agents with limited cognitive precision might handle divergent reward structures. We demonstrate that the St. Petersburg series can become inert under this coarse addition for a suitably constructed partition. The approach may also have broader applications in behavioral modeling and the study of machine reasoning under perceptual limitations.
This investigation establishes a formal equivalence between the generalized Black-Scholes equation under a Quadratic Normal Volatility (QNV) specification and the stationary Schrödinger equation for a hyperbolic Pöschl-Teller potential. A sequence of canonical transformations maps the financial pricing operator to a quantum Hamiltonian, revealing the volatility smile as a direct manifestation of diffusion on a hyperbolic manifold whose geometry is classified by the discriminant of the QNV polynomial. We perform a complete spectral analysis of the financial Hamiltonian, deriving its discrete and continuous spectra and constructing the pricing kernel from the resulting eigenfunctions, which are given by classical special functions. This analytical framework, grounded in a gauge-theoretic perspective, furnishes a non-trivial benchmark for derivative pricing and provides a fundamental geometric interpretation of market anomalies. Future research trajectories toward integrable systems and formal field-theoretic analogies are identified.
We propose an algebro-geometric interpretation of the Schur and Macdonald indices of four-dimensional $\mathcal{N}=2$ superconformal field theories (SCFTs). We conjecture that there exists an affine scheme $X$ such that the Hilbert series of the (appropriately-graded) arc space of its polynomial ring $J_\infty(\mathbb{C}[X])$ encodes the indices. Distinct local descriptions of a (singular) point correspond to distinct choices of $X$, giving rise to a family of $\mathcal{N}=2$ SCFTs each without a Higgs branch. These local descriptions directly translate into nilpotency relations in the operator product expansions. We test our conjecture across a variety of (generalized) Argyres-Douglas (AD) theories.
We introduce the notion of higher Berry connection and curvature in the space of conformal boundary conditions in (1+1)d conformal field theories (CFT), related to each other by exactly marginal boundary deformations, forming a "boundary conformal manifold." Our definition builds upon previous works on tensor networks, such as matrix product states (MPS), where the triple inner product or multi-wavefunction overlap plays the key geometric role. On the one hand, our boundary conformal field theory (BCFT) formulation of higher Berry phase provides a new analytic tool to study families of invertible phases in condensed matter systems. On the other hand, it uncovers a new geometric structure on the moduli space of conformal boundary conditions, beyond the usual Riemannian structure defined through the Zamolodchikov metric. When the boundary conformal manifold has an interpretation as the position moduli space of a D-brane, our higher Berry connection coincides with the NS-NS $B$-field in string theory. The general definition does not require such an interpretation and is formulated purely field-theoretically, in terms of correlation functions of boundary-condition-changing (bcc) operators. We also explore a connection between higher Berry connections and functional Berry connections in the loop spaces of boundary conformal manifolds.
In this work, we study the connection between two subjects: the space of conformal boundary conditions in boundary conformal field theories (BCFTs) and the space of gapped systems characterized by higher Berry phases. We explore this connection by analyzing multi-parameter spectral flow in Dirac fermion BCFTs with continuously parametrized conformal boundary conditions, which are introduced by coupling a CFT to a family of gapped systems. When the gapped systems belong to a nontrivial higher Berry class, the associated conformal boundary conditions induce a flow of the ordinary Berry curvature, resulting in a Chern number pump in the Fock space of the BCFT. This phenomenon is the BCFT analog of Berry curvature flow in one-dimensional parametrized gapped systems, where the flow occurs in real space. Building on this correspondence, we introduce the notions of higher Berry curvature and higher Berry invariants within the BCFT framework. Our results provide a new perspective for studying the topological properties of families of conformal boundary states and gapped ground states: if a family of gapped states belongs to a nontrivial higher Berry class, then the corresponding entanglement Hamiltonians exhibit a multi-parameter spectral flow that carries Berry curvature in the Fock space.
The definition of metastable states is an ubiquitous task in the design and analysis of molecular simulation, and is a crucial input in a variety of acceleration methods for the sampling of long configurational trajectories. Although standard definitions based on local energy minimization procedures can sometimes be used, these definitions are typically suboptimal, or entirely inadequate when entropic effects are significant, or when the lowest energy barriers are quickly overcome by thermal fluctuations. In this work, we propose an approach to the definition of metastable states, based on the shape-optimization of a local separation of timescale metric directly linked to the efficiency of a class of accelerated molecular dynamics algorithms. To realize this approach, we derive analytic expressions for shape-variations of Dirichlet eigenvalues for a class of operators associated with reversible elliptic diffusions, and use them to construct a local ascent algorithm, explicitly treating the case of multiple eigenvalues. We propose two methods to make our method tractable in high-dimensional systems: one based on dynamical coarse-graining, the other on recently obtained low-temperature shape-sensitive spectral asymptotics. We validate our method on a benchmark biomolecular system, showcasing a significant improvement over conventional definitions of metastable states.
While average treatment effects (ATE) and conditional average treatment effects (CATE) provide valuable population- and subgroup-level summaries, they fail to capture uncertainty at the individual level. For high-stakes decision-making, individual treatment effect (ITE) estimates must be accompanied by valid prediction intervals that reflect heterogeneity and unit-specific uncertainty. However, the fundamental unidentifiability of ITEs limits the ability to derive precise and reliable individual-level uncertainty estimates. To address this challenge, we investigate the role of a cross-world correlation parameter, $ \rho(x) = cor(Y(1), Y(0) | X = x) $, which describes the dependence between potential outcomes, given covariates, in the Neyman-Rubin super-population model with i.i.d. units. Although $ \rho $ is fundamentally unidentifiable, we argue that in most real-world applications, it is possible to impose reasonable and interpretable bounds informed by domain-expert knowledge. Given $\rho$, we design prediction intervals for ITE, achieving more stable and accurate coverage with substantially shorter widths; often less than 1/3 of those from competing methods. The resulting intervals satisfy coverage guarantees $P\big(Y(1) - Y(0) \in C_{ITE}(X)\big) \geq 1 - \alpha$ and are asymptotically optimal under Gaussian assumptions. We provide strong theoretical and empirical arguments that cross-world assumptions can make individual uncertainty quantification both practically informative and statistically valid.
Zak-transform based orthogonal time frequency space (Zak-OTFS) is a delay-Doppler (DD) domain modulation scheme in which the signal processing is carried out in the DD domain. The channel when viewed in the DD domain is predictable. However, even with Zak-OTFS, pilots need to be sent periodically, albeit at a lower rate. In this paper, we propose a differential communication scheme for Zak-OTFS systems that alleviates the need for periodic pilot transmission. Towards this, we analytically show that the detected data can be used as a pilot and that the channel estimate obtained from the detected data can enable further detection enabling the "differential" aspect of the communication. Specifically, we leverage the prediction capability of the DD channel in Zak-OTFS to use the channel estimate (obtained from detected data symbols treated as pilots) in the previous instant to detect data in the next instant and propagate this forward. The advantages are two fold. First, it allows the data symbols to enjoy higher energy since the energy that would otherwise be required for pilot symbols can also be allocated to data symbols. Second, it allows for full spectral efficiency compared to point or embedded pilots. Comparison with the full spectral efficiency achieving spread pilot scheme shows that the proposed method achieves better bit-error rate at lower complexity.
Platform trials evaluate multiple experimental treatments against a common control group (and/or against each other), which often reduces the trial duration and sample size. Bayesian platform designs offer several practical advantages, including the flexible addition or removal of experimental arms using posterior probabilities and the incorporation of prior/external information. Regulatory agencies require that the operating characteristics of Bayesian designs are assessed by estimating the sampling distribution of posterior probabilities via Monte Carlo simulation. It is computationally intensive to repeat this simulation process for all design configurations considered, particularly for platform trials with complex interim decision procedures. In this paper, we propose an efficient method to assess operating characteristics and determine sample sizes as well as other design parameters for Bayesian platform trials. We prove theoretical results that allow us to model the joint sampling distribution of posterior probabilities across multiple endpoints and trial stages using simulations conducted at only two sample sizes. This work is motivated by design complexities in the SSTARLET trial, an ongoing Bayesian adaptive platform trial for tuberculosis preventive therapies (ClinicalTrials.gov ID: NCT06498414). Our proposed design method is not only computationally efficient but also capable of accommodating intricate, real-world trial constraints like those encountered in SSTARLET.
Returning walks on a lattice are sequences of moves that start at a given lattice site and return to the same site after $n$ steps. Determining the total number of returning walks of a given length $n$ is a typical graph-theoretical problem with connections to lattice models in statistical and condensed matter physics. We derive analytical expressions for the returning walk numbers on the eleven two-dimensional Archimedean lattices by developing a connection to the theory of Bloch energy bands. We benchmark our results through an alternative method that relies on computing the moments of adjacency matrices of large graphs, whose construction we explain explicitly. As a condensed matter physics application, we use our formulas to compute the density of states of tight-binding models on the Archimedean lattices. While the Archimedean lattices provide a sufficiently rich structure and are chosen here for concreteness, our techniques can be generalized straightforwardly to other two- or higher-dimensional Euclidean lattices.
In this paper, we investigate on the modeling of demand response activities between the single aggregator and multiple participating consumers. The model incorporates the bilevel structure that naturally occurs in the information structure and decision sequence, where the aggregator assumes the role of a leader and the participating consumers play the role of followers. The proposed model is demonstrated to be effective in load control, helping the aggregator to meet the target reduction while the consumers pay cheaper electricity bill.
Constructing a control invariant set with an appropriate shape that fits within a given state constraint is a fundamental problem in safety-critical control but is known to be difficult, especially for large or complex spaces. This paper introduces a safe control framework of utilizing PCBF: continuously parametrized control barrier functions (CBFs). In PCBF, each choice of parameter corresponds to a control invariant set of relatively simple shape. Invariance-preserving control is done by dynamically selecting a parameter whose corresponding invariant set lies within the safety bound. This eliminates the need for synthesizing a single complex CBF that matches the entire free space. It also enables easier adaptation to diverse environments. By assigning a differentiable dynamics on the parameter space, we derive a lightweight feedback controller based on quadratic programming (QP), namely PCBF-QP. We also discuss on how to build a valid PCBF for a class of systems and how to constrain the parameter so that the invariant set does not exceed the safety bound. The concept is also extended to cover continuously parametrized high-order CBFs, which is called high-order PCBF. Finally, simulation experiments are conducted to validate the proposed approach.
In this work we consider the problem of constructing flow evolutions leading to a self-similar energy cascade consistent with Kolmogorov's statistical theory of turbulence. As a first step in this direction, we focus on the one-dimensional viscous Burgers equation as a toy model. Its solutions exhibiting self-similar behavior, in a precisely-defined sense, are found by framing this problems in terms of PDE-constrained optimization. The main physical parameters are the time window over which self-similar behavior is sought (equal to approximately one eddy turnover time), viscosity (inversely proportional to the ``Reynolds number") and an integer parameter characterizing the distance in the Fourier space over which self-similar interactions occur. Local solutions to this nonconvex PDE optimization problems are obtained with a state-of-the-art adjoint-based gradient method. Two distinct families of solutions, termed viscous and inertial, are identified and are distinguished primarily by the behavior of enstrophy which, respectively, uniformly decays and grows in the two cases. The physically meaningful and appropriately self-similar inertial solutions are found only when a sufficiently small viscosity is considered. These flows achieve the self-similar behaviour by a uniform steepening of the wave fronts present in the solutions. The methodology proposed and the results obtained represent an encouraging proof of concept for this approach to be employed to systematically search for self-similar flow evolutions in the context of three-dimensional turbulence.
Time-dependent partial differential equations are ubiquitous in physics-based modeling, but they remain computationally intensive in many-query scenarios, such as real-time forecasting, optimal control, and uncertainty quantification. Reduced-order modeling (ROM) addresses these challenges by constructing a low-dimensional surrogate model but relies on a fixed discretization, which limits flexibility across varying meshes during evaluation. Operator learning approaches, such as neural operators, offer an alternative by parameterizing mappings between infinite-dimensional function spaces, enabling adaptation to data across different resolutions. Whereas ROM provides rigorous numerical error estimates, neural operator learning largely focuses on discretization convergence and invariance without quantifying the error between the infinite-dimensional and the discretized operators. This work introduces the reduced-order neural operator modeling (RONOM) framework, which bridges concepts from ROM and operator learning. We establish a discretization error bound analogous to those in ROM, and get insights into RONOM's discretization convergence and discretization robustness. Moreover, two numerical examples are presented that compare RONOM to existing neural operators for solving partial differential equations. The results demonstrate that RONOM using standard vector-to-vector neural networks achieves comparable performance in input generalization and superior performance in both spatial super-resolution and discretization robustness, while also offering novel insights into temporal super-resolution scenarios.