📑

학술

arXiv 등 학술 논문. CC-BY 라이선스로 자유 재사용 가능 — 출처표시 시 상업 사용 OK.

총 12,367건

Schemata, Cyclic Proofs and Herbrand Systems

arXiv:2606.23040v2 Announce Type: replace-cross Abstract: Inductive proofs can be represented by proof schemata, a formalism that represents infinite sequences of proofs by recursive definitions. Since proof schemata avoid the explicit application of induction rules, they admit novel applications, one of which is the realization of Herbrand's theorem in the presence of induction. In this paper, we develop a new type of proof schema based on point transition systems. For skolemized proof schemata without quantified cuts, so-called Herbrand systems, that is, schemata of Herbrand instances of quantified formulas, can be computed. Herbrand systems also allow the representation of schemata of Herbrand sequents, thereby realizing Herbrand's theorem for proof schemata. We compare proof schemata with cyclic proofs and define a transformation from a large class of cyclic proofs to proof schemata. Finally, we show that proof schemata based on point transition systems are capable of proving the 2-Hydra statement, a well-known example that is provable by the cyclic proof system CLKID\omega but not in LKID.

arXiv Math

Structural identifiability of partially-observed stochastic processes: from single-particle trajectories to total particle density data

arXiv:2605.13504v2 Announce Type: replace-cross Abstract: The increasing availability of experimental data has intensified interest in calibrating stochastic models, raising fundamental questions about parameter identifiability. Structural identifiability determines whether parameters can be uniquely recovered from idealised, noise-free data, a prerequisite to allow for parameter estimation in real-world scenarios. However, existing methods to assess structural identifiability are not generally applicable to stochastic processes. We develop a methodology to analyse structural identifiability for a class of stochastic processes. We investigate how structural identifiability depends on the type of available data, distinguishing between single-particle trajectories and total particle density measurements. For trajectory data, we use the particle-based model description that explicitly represents single-particle dynamics. For population-level data, we derive a partial differential equation model representation, that describes the evolution of total particle density, and apply a differential algebra approach, common to ordinary differential equation analysis. We further introduce a method to study information arising from the initial condition, based on using the characteristic equations to construct a Taylor expansion of the particle density evolution. We apply our methodology to an example model and show that it is structurally identifiable from single-particle trajectory data but not from total particle density data, demonstrating that parameter identifiability depends on the type of data available.

arXiv Math

Adequate Losses via Quantitative Linear Logic

arXiv:2605.13348v3 Announce Type: replace-cross Abstract: As neural components are increasingly embedded in existing symbolic software -- including safety-critical systems -- the question arises of how to specify and enforce the safety of the newly introduced neural parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean interpretation, but also to training and optimisation. The latter calls for a quantitative interpretation of the logical syntax, subject to further requirements such as smoothness and differentiability. Moreover, the qualitative and quantitative sides of the logic must share a unifying proof-theoretic and categorical semantics. Finally, the new logic should link cleanly to the substructural and program logics that underpin the verification of existing symbolic programs. In this paper, we present a logic that ticks all of these boxes. We introduce a family of calculi, pQLL, indexed by a hardness degree $p$, prove a cut-elimination theorem for them, and establish completeness with respect to enriched residuated `soft' lattices. At $p = \infty$, \pQLL reduces to multiplicative additive linear logic (MALL), and provability in pQLL converges to provability in MALL as $p \to \infty$. We express optimisation objectives in the syntax of this logic and prove the quantitative adequacy of neuro-symbolic loss functions -- a result that has eluded the neuro-symbolic machine learning community for nearly a decade.

arXiv Math

Toward a Characterization of Simulation Between Arithmetic Theories

arXiv:2604.27787v2 Announce Type: replace-cross Abstract: We study when a sound arithmetic theory $\mathcal S\supseteq S^1_2$ with polynomial-time decidable axioms efficiently proves the bounded consistency statements $Con_{\mathcal S+\phi}(n)$ for a true sentence $\phi$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S+\phi$. The paper gives two unconditional constraints on possible characterizations. First, for finitely axiomatized sequential $\mathcal S$, if $EA\vdash Con_{\mathcal S}\rightarrow Con_{\mathcal S+\phi}$, then $\mathcal S$ interprets $\mathcal S+\phi$, implying $\mathcal S\vdash^{n^{O(1)}}Con_{\mathcal S}(p(n))\rightarrow Con_{\mathcal S+\phi}(n)$ for some polynomial $p$, and hence $\mathcal S\vdash^{n^{O(1)}}Con_{\mathcal S+\phi}(n)$. Second, if $\mathcal S$ fails to simulate $\mathcal S+\phi$ for some true $\phi$, then for all sufficiently large $k$ it also fails to simulate $S^1_2+\phi_{BB}(k)$, where $\phi_{BB}(k)$ asserts the exact value of the $k$-state Busy Beaver function. Thus any hard true extension yields a canonical Busy Beaver witness to nonsimulation. The paper's central conjectural proposal is: for sound, finitely axiomatized sequential $\mathcal S$, if $EA\not\vdash Con_{\mathcal S}\rightarrow Con_{\mathcal S+\phi}$, then for every constant $c>0$, $\mathcal S\not\vdash^{n^c}Con_{\mathcal S+\phi}(n)$. Under this proposal, hardness follows when $\phi$ is $Con_{\mathcal S}$ or a Kolmogorov-randomness axiom. The latter yields further conjectural consequences and extensions.

arXiv Math

Geometry of tail allocation in conformal prediction intervals

arXiv:2604.25202v2 Announce Type: replace-cross Abstract: Lower and upper errors of a two-sided conformal prediction interval can have different scientific consequences. The division of target miscoverage between the two endpoints determines the corresponding tail-specific guarantees and can alter interval length at first order when tail scales differ. We characterize this allocation-length relation after separate one-sided split calibration, which preserves the tail-specific guarantees and marginal coverage whenever the allocation is selected independently of the calibration sample. Tail-quantile response to proportional rescaling determines the resulting length geometry. For regularly varying tails, normalized length converges to $g_\gamma(c)=c^{-\xi}+\gamma(1-c)^{-\xi}$, where $c$ is the upper-tail allocation fraction, $\xi$ is the tail index, and $\gamma$ is the lower-to-upper tail-scale ratio. A dominant tail produces a boundary optimum and makes the equal-tail interval asymptotically $2^\xi$ times as long as the optimum. Comparable tails produce an interior optimum, with equal-tail allocation optimal only at matching scales. An empirical allocation rule attains the corresponding optimum without estimating tail parameters. In the de Haan class the effect moves to an additive scale. Calibration resolution determines whether ordinary ranks can realize these allocations. When calibration tail counts remain bounded, two-sided rank feasibility also constrains the allocation. Tail homogeneity transfers the length relation over covariates, while opposite dominant tails preclude one globally efficient allocation.

arXiv Math

Critical dimensions and small cycle dominance from all-orders asymptotics of $d$-matrix theory

arXiv:2603.29610v2 Announce Type: replace-cross Abstract: Supersymmetric sectors of $\mathcal{N}=4$ super-Yang-Mills theory motivate the study of the partition function for the counting of gauge-invariant functions of $d=2,3$ matrices transforming under the adjoint action of $U(N)$. The partition function $ \mathcal{Z}_d ( x) $ in the large $N$ limit has a known Hagedorn phase transition at $ x = d^{-1} $ which provides a simple model for the phase structure of the thermal partition function of SYM. We study the all-orders asymptotic expansion of $ \mathcal{Z}_d(x)$ based on a geometric picture of concentric circles of poles in the complex plane accumulating in a natural boundary at $|x| =1$. We find that the order by order structure has a precise combinatorial interpretation organized in terms of increasing cycle size of permutations arising in the enumeration of the invariants. We refer to this organization as small-cycle dominance, and find that it extends to refined versions of the partition functions depending on several complex variables. An analysis of the coefficients in the asymptotic expansion of $ \mathcal{Z}_d(x) $ using the modular property of the Dedekind eta function reveals that the asymptotic expansion is actually convergent for $d\ge d_{ \rm crit } = 13$. A fermionic version of $\mathcal{Z}_d (x)$ has an analogous critical dimension of $ d_{ \rm crit} = 7$. This distinction indicates that the partition functions of the matrix models can be completely reconstructed from their high-energy (UV) limit for $d\ge d_{ \rm crit}$ whereas additional input is required to reconstruct the exact coefficients of the low-energy (IR) expansion for $2\le d \le d_{ \rm crit } -1 $.

arXiv Math

Stationary Online Contention Resolution Schemes

arXiv:2603.21532v2 Announce Type: replace-cross Abstract: Online contention resolution schemes (OCRSs) are a central tool in Bayesian online selection and resource allocation: they convert fractional ex-ante relaxations into feasible online policies while preserving each marginal probability up to a constant factor. Despite their importance, designing (near) optimal OCRSs is often technically challenging, and many existing constructions rely on indirect reductions to prophet inequalities and LP duality, resulting in algorithms that are difficult to interpret or implement. In this paper, we introduce "stationary online contention resolution schemes (S-OCRSs)," a permutation-invariant class of OCRSs in which the distribution of the selected feasible set is independent of arrival order. We show that S-OCRSs admit an exact distributional characterization together with a universal online implementation. We then develop a general `maximum-entropy' approach to construct and analyze S-OCRSs, reducing the design of online policies to constructing suitable distributions over feasible sets. This yields a new technical framework for designing simple and possibly improved OCRSs. We demonstrate the power of this framework across several canonical feasibility environments. In particular, we obtain an improved $(3-\sqrt{5})/2$-selectable OCRS for bipartite matchings, attaining the independence benchmark conjectured to be optimal and yielding the best known prophet inequality for this setting. We also obtain a $1-\sqrt{2/(\pi k)} + O(1/k)$-selectable OCRS for $k$-uniform matroids and a simple, explicit $1/2$-selectable OCRS for weakly Rayleigh matroids (including all $\mathbb{C}$-representable matroids such as graphic and laminar). While these guarantees match the best known bounds, our framework also yields concrete and systematic constructions, providing transparent algorithms in settings where previous OCRSs were implicit or technically involved.

arXiv Math

Quasinormal Modes of Extremal Reissner-Nordstrom Black Holes via Seiberg-Witten Quantization

arXiv:2603.19168v3 Announce Type: replace-cross Abstract: We study the scalar perturbations of asymptotically flat extremal Reissner-Nordstr\"om black holes via the quantum Seiberg-Witten geometry of $\mathcal{N}=2$ SU(2) gauge theory with $N_f=2$ flavors. The radial master equation, governed by a double confluent Heun equation, is exactly mapped to the quantum Seiberg-Witten curve, providing an exact quantization condition derived from the non-perturbative Nekrasov-Shatashvili free energy. Analytically, this exact dictionary unveils precise gauge-theoretic interpretations for critical physical thresholds, demonstrating that the superradiance and mass decoupling limits naturally reduce the master equation to the Whittaker equation and the reduced doubly confluent Heun equation (the latter corresponds to the SW geometry of the $\mathcal{N}=2$ SU(2) gauge theory with $N_f=1$), respectively. At the strict extremal limit, the coalescence of horizons induces a topological singularity that complicates the spectral analysis. By accommodating this irregular singularity, our geometric framework resolves the singularity coalescence and enables the extraction of the discrete global quasinormal mode. As our main contribution, we provide the first non-perturbative evaluation of the quasinormal modes spectrum for simultaneously charged and massive scalar fields directly at strict extremity. Furthermore, our analytical results reproduce numerical benchmarks for both neutral and charged massless probes, and naturally capture quasi-resonance behaviors.

arXiv Math

Bidirectional Interpolation for the Lambda-Calculus: Revisiting and Formalising Craig-\v{C}ubri\'c Interpolation

arXiv:2603.03083v2 Announce Type: replace-cross Abstract: Craig's Interpolation theorem has a wide range of applications, from mathematical logic to computer science. Proof-theoretic techniques for establishing interpolation usually follow a method first introduced by Maehara for the Sequent Calculus and then adapted by Prawitz to Natural Deduction. The result can be strengthened to a proof-relevant version, taking proof terms into account: this was first established by \v{C}ubri\'c in the simply-typed lambda-calculus with sums and more recently in linear, classical and intuitionistic sequent calculi. We give a new proof of \v{C}ubri\'c's proof-relevant interpolation theorem by building on principles of bidirectional typing, and formalise it in Rocq.

arXiv Math

Twisting BFSS & IKKT

arXiv:2602.22318v3 Announce Type: replace-cross Abstract: In this note we initiate the study of ``twisted holography'' for the dualities involving the BFSS matrix quantum mechanics and the IKKT matrix model in their $N \rightarrow \infty$ limits. We identify the admissible twists of each model, compute their cohomology in the BV-BRST formalism, and identify them -- in the planar limit and in perturbation theory around the trivial background -- with corresponding twists of IIA and IIB string theories, respectively. The twisted gravitational duals make manifest certain infinite dimensional symmetry algebras. In the BFSS example, the dual IIA supergravity twists are also obtained as certain zero mode truncations of the minimal (1/16-BPS) and maximal (1/4-BPS) twists of eleven-dimensional supergravity.

arXiv Math

Parity-dependent double degeneracy and spectral statistics in the projected dice lattice

arXiv:2602.11844v2 Announce Type: replace-cross Abstract: We investigate the spectral statistics of an interacting fermionic system derived by projecting the Hubbard interaction onto the two lowest-energy, degenerate flat bands of the dice lattice subjected to a $\pi$-flux. Surprisingly, the distributions of level spacings and gap ratios correspond to distinct Gaussian ensembles, depending on the parity of the particle number. For an even number of particles, the spectra conform to the Gaussian Orthogonal Ensemble, as expected for a time-reversal-symmetric Hamiltonian. In stark contrast, the odd-parity sector exhibits exact double degeneracy of all eigenstates even after resolving all known symmetries, and the Gaussian Unitary Ensemble accurately describes the spacing distribution between these doublets. The simultaneous emergence of two different random-matrix ensembles within a single physical system constitutes an unprecedented finding, opening new avenues for both random matrix theory and flat-band physics.

arXiv Math

Thermodynamic Limits of Proof

arXiv:2601.15571v5 Announce Type: replace-cross Abstract: Every irreversible recorded distinction has a positive thermodynamic work floor. Landauer's principle supplies the ideal bound $\varepsilon\ge k_B T\ln 2$ per irreversible bit, experimentally verified to $\pm 10\%$. Proof available to an agent is checkable information for that agent: some substrate must produce, retain, and expose evidence that excludes answer-changing alternatives. A finite detector array operating at temperature $T$ for finite time has finite signal-acquisition capacity. Combining finite causal access, positive retained-record cost, and exact lower bounds on required records gives the Physical Counting Impossibility Theorem: no fixed-budget substrate can provide universal exact proof once the retained-record lower bound exceeds the declared budget. The theorem requires exactly $B0$. An answer reports a value; proof supplies checkable grounds for accepting it. A reversible device may compute an answer and erase its scratch history, but proof requires retained, inspectable records. A global answer register, oracle response, entanglement witness, finite survey catalog, or trusted device output supplies proof only through an interface that exposes the relevant grounds to the verifier. A proposed interface must identify the retained-record lower-bound family $R(n)$ it induces. Sound operational claims about efficient solvability inherit the same finite-budget obstruction when their acceptance would license universal exact proof. Substrate-free derivability has proof status only when a physical verification event makes it available to an agent.

arXiv Math

Exact general solutions for cosmological scalar field evolution in a vacuum-energy dominated expansion

arXiv:2601.15226v3 Announce Type: replace-cross Abstract: We derive exact general solutions (as opposed to attractor particular solutions) for the evolution of a scalar field $\phi$ in a universe dominated by a background fluid with equation of state parameter $w_B = -1$, extending earlier work on exact solutions with $w_B > -1$. Straightfoward exact solutions exist when the evolution is described by a linear differential equation, corresponding to constant, linear, and quadratic potentials. In the nonlinear case, exact solutions are derived for $V = V_0\ln \phi$, $V = V_0 \phi^{1/2}$ and $V = V_0/\phi$, and the logarithmic potential also yields an exact first integral. These complicated parametric solutions are considerably less useful than those derived previously for a universe dominated by a barotropic fluid such as matter or radiation with $w_B > -1$. However, we generalize the slow-roll approximation and show that it applies to all sufficiently flat potentials in the case of a vacuum-dominated expansion, while it never applies when the universe is dominated by a background fluid with $w_B > -1$.

arXiv Math

Walk based Laplacians for Modeling Diffusion on Complex Networks

arXiv:2601.11338v2 Announce Type: replace-cross Abstract: We develop a novel framework for modeling diffusion on complex networks by constructing Laplacian-like operators based on walks around a graph. Our approach introduces a parametric family of walk-based Laplacians that naturally incorporate memory effects by excluding or downweighting backtracking trajectories, where walkers immediately revisit nodes. The framework includes: (i) walk-based Laplacians that count all traversals in the network; (ii) nonbacktracking variants that eliminate immediate reversals; and (iii) backtrack-downweighted variants that provide a continuous interpolation between these two regimes. We establish that these operators extend the definition of the standard Laplacian and also preserve some of its properties. We present efficient algorithms using Krylov subspace methods for computing them, ensuring applicability of our proposed framework to large networks. Extensive numerical experiments on real-world networks validate the modeling flexibility of our approach and demonstrate the computational efficiency of the proposed algorithms, including GPU acceleration.

arXiv Math

A Weak Penalty Neural ODE for Learning Chaotic Dynamics from Noisy Time Series

arXiv:2511.06609v4 Announce Type: replace-cross Abstract: The accurate forecasting of complex, high-dimensional dynamical systems from observational data is a fundamental task across numerous scientific and engineering disciplines. A significant challenge arises from noise-corrupted measurements, which severely degrade the performance of data-driven models. In chaotic dynamical systems, where small initial errors amplify exponentially, it is particularly difficult to develop a model from noisy data that achieves short-term accuracy while preserving long-term invariant properties. To overcome this, we consider the weak formulation as a complementary approach to the classical $L2$-loss function for training models of dynamical systems. We empirically verify that the weak formulation, with a proper choice of test function and integration domain, effectively filters noisy data. This insight explains why a weak form loss function is analogous to fitting a model to filtered data and provides a practical way to parameterize the weak form. Subsequently, we demonstrate how this approach overcomes the instability and inaccuracy of standard Neural ODE (NODE) in modeling chaotic systems. Through numerical examples, we show that our proposed training strategy, the Weak Penalty NODE, is computationally efficient, solver-agnostic, and yields accurate and robust forecasts across benchmark chaotic systems and a real-world climate dataset.

arXiv Math

A Robust EDM Optimization Approach for 3D Single-Source Localization with Angle and Range Measurements

arXiv:2510.13498v3 Announce Type: replace-cross Abstract: Accurate source localization in Multi-Platform Radar Networks (MPRNs) benefits from exploiting both range and angle measurements under robust estimation. In this paper, we propose a robust Euclidean distance matrix (EDM) optimization model that simultaneously integrates range measurements, angle information, and the least absolute deviation ($\ell_1$-norm) criterion for the case of 3D single-source localization (3DSSL). A key theoretical contribution of this work is the rigorous reformulation of {existing} 3D angle measurements into simple box constraints on the Euclidean distances. Unlike previous approximations, we achieve this by reducing each of the 3D angle measurements to a two-dimensional nonlinear optimization problem, whose global minimum and maximum solutions can be characterized and utilized to get the lower and upper bounds of the distances from the unknown source to the sensors. To solve the resulting rank-constrained EDM problem, we develop an efficient algorithm based on the majorization penalty method. Extensive numerical experiments confirm that the new EDM model significantly outperforms leading solvers in terms of localization accuracy and computational efficiency, particularly in low Signal-to-Noise Ratio (SNR) scenarios.

arXiv Math

An exactly solvable asymmetric simple inclusion process

arXiv:2510.09191v2 Announce Type: replace-cross Abstract: We study a generalization of the asymmetric simple inclusion process (ASIP) on a periodic one-dimensional lattice, where the integers in the particles rates are deformed to their $t$-analogues. We call this the $(q, t, \theta)$~ASIP, where $q$ is the asymmetric hopping parameter and $\theta$ is the diffusion parameter. We show that this process is a misanthrope process, and consequently the steady state is independent of $q$. We compute the steady state, the one-point correlation and the current in the steady state. In particular, we show that the single-site occupation probabilities follow a \emph{beta-binomial} distribution at $t=1$. We compute the two-dimensional phase diagram in various regimes of the parameters $(t, \theta)$ and perform simulations to justify the results. We also show that a modified form of the steady state weights at $t \neq 1$ satisfy curious palindromic and antipalindromic symmetries. Lastly, we define an enriched process at $t=1$ and $\theta$ an integer which projects onto the $(q, 1, \theta)$~ASIP and whose steady state is uniform, which may be of independent interest.

arXiv Math

Modeling and Control of Deep Sign-Definite Dynamics with Application to Hybrid Powertrain Control

arXiv:2509.19869v2 Announce Type: replace-cross Abstract: Data-driven control increasingly relies on deep models for complex systems whose first-principles models are difficult to obtain. For reliable deployment, however, learned dynamics should respect physical structure and lead to tractable optimal control. We introduce sign constraints, namely sign restrictions on Jacobian entries, as a unified description of monotonicity, positivity, and sign-definiteness. For exactly linearizable deep dynamics, we provide structural conditions and neural-network parameterizations that enforce these constraints by construction. The same structure also allows model predictive control to be formulated as a convex quadratic program or as a convex relaxation, yielding a unique optimizer and a Lipschitz continuous control law. Applications to a three-tank system and a hybrid powertrain demonstrate that the proposed approach offers improved extrapolation performance and smoother control inputs compared with competing nonconvex formulations.

arXiv Math

Localization of strings on group manifolds

arXiv:2506.20028v3 Announce Type: replace-cross Abstract: We compute the partition function of the WZW model with target a compact Lie group $G$ by adapting a method used by Choi and Takhtajan to compute the heat kernel of the group manifold. The basic idea is to compute the partition function of a supersymmetric version of the WZW model using a form of supersymmetric localization and then use the fact that, since the fermions of the supersymmetric WZW model are actually decoupled from the bosons, this also determines the partition function of the purely bosonic WZW model. The result is a formula for the partition function as a sum over contributions from abelian classical solutions. We verify for $G=SU(2)$ that this formula agrees with the result for the same partition function that comes from the Weyl-Kac character formula. We extend the method of supersymmetric localization to certain related models such as the $SL(2,\mathbb{R})$ WZW model and a Wick-rotated version of this model in which the target space is hyperbolic three-space $H_3^+$.

arXiv Math

Primal-dual algorithm for contextual stochastic combinatorial optimization

arXiv:2505.04757v2 Announce Type: replace-cross Abstract: This paper introduces a novel approach to contextual stochastic optimization, integrating operations research and machine learning to address decision-making under uncertainty. Traditional methods often fail to leverage contextual information, which underscores the necessity for new algorithms. In this study, we utilize neural networks with combinatorial optimization layers to encode policies. Our goal is to minimize the empirical cost, which is estimated from past data on uncertain parameters and contexts. To that end, we present a surrogate learning problem and a generic primal-dual algorithm that is applicable to various combinatorial settings in stochastic optimization. Our approach extends classic Fenchel--Young loss results and introduces a new regularization method using sparse perturbations on the distribution simplex. This allows for tractable updates in the original space and can accommodate diverse objective functions. We establish sublinear convergence for the exact linear-parametric version and provide a bound on the non-optimality of the resulting policy in terms of the empirical cost. Experiments on three contextual stochastic optimization problems show that our algorithm is efficient and scalable, achieving performance comparable to state-of-the-art baselines with significantly reduced computational requirements.

1 / 619다음 →

arXiv Math