Logic
Lower Bounds on Inverse Cellular Automata via Proof Complexity
Maryia Kapytka
We study the complexity of inverse cellular automata on configurations of bounded size. Deciding injectivity in this setting is co-NP-complete by a
theorem of Durand. We give a simpler proof of this
theorem by a direct reduction from UNSAT to this problem, avoiding more complicated intermediate constructions. We also show that one direction of the reduction can be formalized in the weak theory of bounded arithmetic $V^0$. Durand's coNP-completeness result allows one to view inverse cellular automata acting on bounded size configurations as propositional proofs, cf. Cavagnetto, and we prove lower bounds on their size. The proof uses known lower bounds for bounded-depth Frege systems together with the Paris–Wilkie translation of arithmetic proofs into propositional proofs, which allows us to transfer proof complexity lower bounds to our setting.
Read the full abstract ▾
Numerical Analysis
Stabilizing the Rayleigh–Ritz procedure by randomization
Nian Shao
Extracting approximate eigenpairs from a prescribed subspace is of fundamental importance in
eigenvalue computation. Although the standard Rayleigh–Ritz procedure is widely used for this purpose, it may suffer from deteriorated convergence of Ritz values and may even fail to produce convergent Ritz vectors, unless the compressed
eigenvalue problem is assumed to be well-conditioned. In this paper, we address the eigenpair extraction problem by introducing a randomized Rayleigh–Ritz procedure. Our analysis shows that, for a simple eigenpair, the
eigenvalue and eigenvector condition numbers of the randomly compressed generalized
eigenvalue problem are, with high probability, comparable to those of the original problem, which yields a reliable approximate eigenpair from the extraction. The result also extends naturally to nonlinear
eigenvalue problems.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.RO
Stein Variational Uncertainty-Adaptive Model Predictive Control
Hrishikesh Sathyanarayan and Ian Abraham
We propose a Stein variational distributionally robust controller for nonlinear dynamical systems with latent parametric uncertainty. The method is an alternative to conservative worst-case ambiguity-set optimization with a deterministic particle-based approximation of a task-dependent uncertainty distribution, enabling the controller to concentrate on parameter sensitivities that most strongly affect closed-loop performance. Our method yields a controller that is robust to latent parameter uncertainty by coupling optimal control with Stein variational inference, and avoiding restrictive parametric assumptions on the uncertainty model while preserving computational parallelism. In contrast to classical DRO, which can sacrifice nominal performance through worst-case design, we find our approach achieves robustness by shaping the control law around relevant uncertainty that are most critical to the task objective. The proposed framework therefore reconciles robust control and variational inference in a single decision-theoretic formulation for broad classes of control systems with parameter uncertainty. We demonstrate our approach on representative control problems that empirically illustrate improved performance-robustness tradeoffs over nominal, ensemble, and classical distributionally robust baselines.
Read the full abstract ▾
Numerical Analysis
Error bounds for splitting methods in unitary problems
Fernando Casas and Ander Murua
Splitting methods constitute a widely used class of numerical integrators for ordinary and partial differential equations, particularly well suited to problems that can be decomposed into simpler subproblems. High-order splitting schemes are available that achieve high accuracy while preserving key qualitative properties of the underlying dynamical system, and are successfully used across a broad range of fields. In this work, we present a systematic analysis of both local and global errors arising from arbitrary splitting methods applied to
unitary problems. Two complementary types of error estimates are derived. The first is expressed in terms of operator norms, while the second is formulated using norms of commutators and can, under suitable assumptions, be extended to certain classes of unbounded operators. Special
attention is devoted to the case where only two operators are involved. The theoretical results are illustrated by deriving explicit error bounds for some representative schemes.
Read the full abstract ▾
Optimization and Control
A Bilevel Integer Programming Approach for the Synchronous Attractor Control Problem
Kyungduk Moon, Kangbok Lee and Loïc Paulevé
Boolean networks are dynamical models of disease development in which the activation levels of genes are represented by binary variables. Given a Boolean network, controls represent mutations or medical treatments that fix the activation levels of selected genes so that all states in every attractor (i.e., long-term recurrent states) satisfy a desired phenotype. Our goal is to enumerate all minimal controls, identifying critical gene subsets in disease development and therapy. This problem has an inherent bilevel integer programming structure and is computationally challenging. We propose an infeasibility-based Benders decomposition, a logic-based Benders framework for bilevel integer programs with multiple subproblems. In our application, each subproblem finds a forbidden attractor of a given length and yields a problem-specific feasibility cut. We also propose an auxiliary IP called subspace separation that finds a Boolean subspace that includes multiple forbidden attractors and thereby strengthens the cut. Numerical experiments show that the resulting
algorithms are much more scalable than state-of-the-art methods and that subspace separation substantially improves performance.
Read the full abstract ▾
Mathematical Physics
Toral Chern-Simons TQFT via Geometric Quantization in Real Polarization
Daniel Galviz
We construct toral Chern-Simons theory with gauge group $\mathbb T=\mathfrak t/\Lambda\cong U(1)^n$ from an even, integral, nondegenerate symmetric bilinear form $K:\Lambda\times\Lambda\to\mathbb Z$ by
geometric quantization via real polarization. We obtain a
unitary extended $(2+1)$-dimensional TQFT by constructing the boundary state spaces and canonical operators and proving that they satisfy the cylinder and gluing axioms. The finite discriminant group $G_K=\Lambda^*/K\Lambda$ arises naturally in the theory and controls the genus-$g$ state spaces. At genus one, the theory recovers the finite quadratic data underlying bosonic Abelian topological order.
Read the full abstract ▾
Group Theory
A residually finite analogue of Kegel's theorem on splitting automorphisms
Alfonso Di Bartolo, K{\i}vanç Ersoy and Giovanni Falcone
Thompson proved that every finite group admitting a fixed-point-free
automorphism of
prime order is nilpotent, and Kegel showed that the same conclusion holds for finite groups admitting a splitting
automorphism of
prime order. Motivated by these results, Sozutov asked whether a \(p'\)-group admitting a splitting
automorphism of
prime order is locally nilpotent if \[ \langle g, g^\varphi, \dots, g^{\varphi^{p-1}} \rangle \] is nilpotent for every \(g \in G\), \cite[Problem 10.59]{kourovka21}. We prove that if \(G\) is a periodic residually finite group admitting a splitting
automorphism of
prime order \(p\) then \(G\) is nilpotent of class bounded in terms of \(p\). This gives an affirmative answer, for residually finite groups, to the problem of Sozutov. We also prove that a possible counterexample to Sozutov's problem cannot be a Tarski monster.
Read the full abstract ▾
Symplectic Geometry
Compactness of Moduli Spaces of Gradient Flow Lines in the Uniform Topology
Tom Stalljohann
We prove a compactness result for gradient flow lines in a general set-up which comprises both the situation of Morse gradient flow lines as well as Floer cylinders converging to a critical submanifold respectively. For the compactness result we have to impose two conditions. Both are readily verified in the Morse case but establishing the second condition in the Floer case poses a technical challenge and relies on an exponential decay estimate for Floer cylinders, with coefficient function continuously depending on the initial loop. This is a result of independent interest.
Read the full abstract ▾
Mathematical Physics
Modeling of point charges with distributions, regularizations, and generalized functions
Guenther Hoermann and Nathalie Tassotti
We apply regularization and generalized function techniques to the classical electromagnetic field of a point-charge, following a strategy by the physicist A. Gsponer 2007-2009, thereby extending it and adding rigor.. We show how the Liénard-Wiechert potential emerges essentially from the basic geometry of Minkowski space, namely by action of the d'Alembertian on a generating vector field, which is defined via a spacetime interval between an observer and the point-charge at retarded proper time. Furthermore, for a charged particle in its rest frame, we discuss generalized functions aspects of the electric monopole,
magnetic dipole, electron singularity, and self-energy, where infinitely large generalized numbers occur whose concrete representations can be applied in field renormalization.
Read the full abstract ▾
Algebraic Geometry
Perverse Schober Structures for Conifold Degenerations
Abdul Rahman
We study a one parameter degeneration of Calabi Yau threefolds whose central fiber contains a single ordinary double point. Using the nearby and vanishing cycle formalism, we construct a canonical perverse object on the singular fiber from the variation morphism between vanishing and nearby cycles. We show that this object restricts to the constant perverse sheaf on the smooth locus and differs from the intersection complex by a single rank one contribution supported at the node. Thus the object isolates the vanishing cycle contribution associated with the conifold degeneration in a canonical sheaf theoretic form. We also explain how this construction aligns with the rank-one Picard Lefschetz phenomenon that appears categorically through spherical monodromy, making it a natural comparison object for the decategorified effect of spherical twists in the ordinary double point case.
Read the full abstract ▾
Numerical Analysis
A Discontinuous Galerkin Scheme for the Cahn-Hilliard Equations with Discrete Maximum Principle for Arbitrary Polynomial Order
Jimmy Kornelije Gunnarsson and Robert Klöfkorn
We propose a structure-preserving discontinuous Galerkin scheme for the Cahn–Hilliard equations with degenerate mobility based on the Symmetric Weighted Interior Penalty formulation. By evaluating the mobility at
cell averages rather than as a piecewise
polynomial, the proposed scheme preserves strict degeneracy and yields a coercivity constant that is independent of the mobility, removing the need for regularization. Moreover, we establish existence of discrete solutions even with degeneracy via a Leray–Schauder fixed-point argument, and show that the scheme satisfies a provable discrete maximum principle at arbitrary
polynomial order $p$ when combined with the Zhang–Shu scaling limiter for $p > 0$ and from the scheme alone for $p = 0$. Mass conservation and energy dissipation are established for the unlimited scheme; for the limited variant, we discuss observed energy dissipation for $p \in \{1,2\}$ and potential theoretical solutions. Numerical experiments confirm optimal convergence rates of order $p$ in $H^1$ for $p \in \{1,2\}$, and of order $p+1$ in $L^2$ in a low amplitude regime with order $2$ for $p=2$ in high amplitude regime and time-dependent low amplitude regime, and validate structure-preserving properties with numerical results.
Read the full abstract ▾
Mathematical Physics · Cross-listed from nucl-th
Exact interpolation between Fick and Cattaneo diffusion in relativistic kinetic theory
Lorenzo Gavassino
We construct a family of exactly solvable relativistic kinetic theories in $1+1$ dimensions whose hydrodynamic sector continuously interpolates between Fick's and Cattaneo's laws of
diffusion. The interpolation is controlled by a single parameter $a\in[0,1]$, which tunes the microscopic scattering dynamics from infinitely soft but infinitely frequent scatterings ($a=0$), reproducing standard
diffusion, to maximally hard but finite-rate scatterings ($a=1$), yielding
hyperbolic Cattaneo-type transport. For intermediate values of $a$, the dynamics combines frequent weak scatterings with rare strong randomizing events, providing a concrete microscopic realization of mixed diffusive-telegraphic behavior. Remarkably, the full quasinormal mode spectrum can be obtained analytically for all $a$. This allows us to track explicitly how purely diffusive modes continuously deform into damped propagating modes as the collision structure is varied.
Read the full abstract ▾
Spectral Theory
On the Effectless Cut Method for Laplacian Eigenvalues in any dimensions
Vincenzo Amato, Nunzia Gavitone and Francesca de Giovanni
In this paper, we study the optimization of the first
Laplacian eigenvalue on axisymmetric doubly connected domains under positive Robin boundary conditions. Under additional
geometric constraints, we prove that spherical shells maximize this
eigenvalue. Our approach combines known isoperimetric inequalities for mixed
Laplacian eigenvalues with a higher-dimensional extension of the effectless cut technique introduced by Hersch to study multiply connected membranes of given area fixed along their boundaries.
Read the full abstract ▾
Analysis of PDEs
Maximal regularity for a compressible fluid-structure interaction system with Navier-slip boundary conditions
Kuntal Bhandari, Imene Aicha Djebour and Šárka Nečasová
We investigate a fluid-structure interaction system in which the dynamics of the fluid is described by the compressible Navier-Stokes equations, while the elastic structure is modeled by a damped plate equation. The fluid evolves in a three-dimensional bounded domain, with the structure occupies a part of its boundary. Instead of standard no-slip boundary conditions, we consider the Navier-slip boundary conditions at the fluid-structure interface as well as at the fixed boundary. We establish the local-in-time existence and uniqueness of strong solutions within $L^{p}-L^{q}$ framework. The existence result is obtained for small time by decoupling the linearized system and employing a cascade strategy combined with the Second Schauder fixed point
theorem, whereas the uniqueness is shown by deriving weak regularity properties for the associated linear coupled operator in a
Hilbert space setting. It is the first result addressing strong solutions for a compressible fluid interacting with a damped plate under Navier-slip boundary conditions.
Read the full abstract ▾
Number Theory
One-loop $p$-adic string theory and the Néron local height function
An Huang and Christian Jepsen
The $p$-adic string worldsheet action on the quotient of the Bruhat-Tits tree of $PGL(2,\mathbb{Q}_p)$ by a genus 1 Schottky group has a dual description on the asymptotic boundary, the Tate curve $\mathbb{Q}_p^\ast/q^\mathbb{Z}$. We show that the two point function of the dual action coincides with the Néron-Tate local height function of the Tate curve.
Read the full abstract ▾
Statistics Theory
From Reverse Detection–Estimation Gaps to Computational Lower Bounds for Norm Approximation
Runshi Tang, Yuefeng Han and Anru R. Zhang
We develop a general reduction scheme that converts reverse detection–estimation gaps into computational lower bounds for norm approximation. If an efficiently computable
estimator has error well below a conjectured computational detection threshold, then a sufficiently accurate norm approximator applied to this
estimator would yield an efficient test, transferring average-case detection hardness to worst-case approximation hardness. The ratio between the detection and estimation scales becomes a lower bound on the achievable approximation factor. We apply the reduction in three settings. Using a previously established reverse gap for high-order cumulant tensors, we obtain a conditional lower bound for
polynomial-time approximation of the order-$d$ tensor spectral norm. We then establish new reverse gaps for the $k$-sparse
matrix spectral norm and a normalized $k$-sparse
matrix cut norm under planted-clique hardness. The resulting lower bounds are of order $\sqrt{k}$ up to a logarithmic factor, matching the simple deterministic $\sqrt{k}$ certificates, whereas previous hardness results for the sparse principal component objective rule out only constant factors. Finally, under a model-specific low-degree
conjecture, a new reverse gap forces polynomially growing approximation factors for the order-$d$ tensor cut norm when $d\ge3$. These results identify reverse detection–estimation gaps as a systematic source of computational lower bounds for norm approximation.
Read the full abstract ▾
Numerical Analysis
Understanding Transformers and Attention Mechanisms: An Introduction for Applied Mathematicians
Michel Fabrice Serret
This document provides a brief introduction to the
attention mechanism used in modern
language models based on the
Transformer architecture. We first illustrate how text is encoded as vectors and how the
attention mechanism processes these vectors to encode semantic information. We then describe Multi-Headed
Attention, examine how the
Transformer architecture is built and look at some of its variants. Finally, we provide a glimpse at modern methods to reduce the computational and
memory cost of
attention, namely KV caching, Grouped Query
attention and Latent
Attention. This material is aimed at the applied mathematics community and was written as introductory presentation in the context of the IPAM Research Collaboration Workshop entitled "Randomized Numerical Linear
Algebra" (RNLA), for the project: "Randomization in
Transformer models".
Read the full abstract ▾
Probability · Cross-listed from cs.DS
Rapid mixing in positively weighted restricted Boltzmann machines
Weiming Feng, Heng Guo and Minji Yang
We show polylogarithmic mixing time bounds for the alternating-scan sampler for positively weighted restricted Boltzmann machines. This is done via analysing the same chain and the Glauber dynamics for
ferromagnetic two-
spin systems, where we obtain new mixing time bounds up to the critical thresholds.
Read the full abstract ▾
Analysis of PDEs
On the equivalence of generalized solution concepts for systems of hyperbolic conservations laws in fluid dynamics
Thomas Eiter, Robert Lasarzik and Emil Wiedemann
We investigate the relation between several generalized solution concepts for nonlinear PDE systems from fluid dynamics. More precisely, we study measure-valued solutions, dissipative weak solutions, and energy-variational solutions. For the incompressible Euler equations, we prove the equivalence of all three concepts, provided that the energy inequality is formulated in the appropriate way. For several important examples of conservation laws arising in fluid dynamics, we establish the equivalence between energy-variational and suitably refined dissipative weak solutions, where the defect measures are controlled sharply by the energy defect. These examples comprise the compressible isentropic Euler system, the Euler–Korteweg system, and the Euler–Poisson system.
Read the full abstract ▾
Numerical Analysis
Physics-informed neural networks for solving two-phase flow problems with moving interfaces
Qijia Zhai, Pengtao Sun, Xiaoping Xie et al. (+2 more)
In this paper, a meshfree method using physics-informed neural networks (PINNs) is developed for solving two-phase flow problems with moving interfaces, where two immiscible fluids bearing different material properties, are separated by a dynamically evolving interface and interact with each other through interface conditions. Two kinds of distinct scenarios of interface motion are addressed: the prescribed interface motion whose moving velocity is explicitly given, and the solution-driven interface motion whose
evolution is determined by the velocity field of two-phase flow. Based upon piecewise deep neural networks and spatiotemporal sampling points/training set in each fluid subdomain, the proposed PINNs framework reformulates the two-phase flow moving interface problem as a least-squares (LS) minimization problem, which involves all residuals of governing equations, interface conditions, boundary conditions and initial conditions. Furthermore, approximation properties of the proposed PINNs approach are analyzed rigorously for the presented two-phase flow model by employing the Reynolds transport
theorem in evolving domains, moreover, a comprehensive error estimation is provided to account for additional complexities introduced by the moving interface and the coupling between fluid dynamics and interface
evolution. Numerical experiments are carried out to illustrate the effectiveness of the proposed PINNs approach for various configurations of two-phase flow moving interface problems, and to validate the theoretical findings as well. A practical guidance is thus provided for an efficient training set distribution when applying the proposed PINNs approach to two-phase flow moving interface problems in practice.
Read the full abstract ▾
All authors Qijia Zhai, Pengtao Sun, Xiaoping Xie, Xingwen Zhu, Chen-Song Zhang
Statistics Theory · Cross-listed from cs.LG
Differentially Private Manifold Denoising
Jiaqi Wu, Yiqing Sun and Zhigang Yao
We introduce a differentially private
manifold denoising framework that allows users to exploit sensitive reference
datasets to correct noisy, non-private query points without compromising
privacy. The method follows an iterative procedure that (i) privately estimates local means and tangent geometry using the reference data under calibrated sensitivity, (ii) projects query points along the privately estimated subspace toward the local mean via corrective steps at each iteration, and (iii) performs rigorous
privacy accounting across iterations and queries using $(\varepsilon,\delta)$-differential
privacy (DP). Conceptually, this framework brings differential
privacy to
manifold methods, retaining sufficient
geometric signal for downstream tasks such as
embedding, clustering, and visualization, while providing formal DP guarantees for the reference data. Practically, the procedure is modular and scalable, separating DP-protected local geometry (means and tangents) from budgeted query-point updates, with a simple scheduler allocating
privacy budget across iterations and queries. Under standard assumptions on
manifold regularity, sampling density, and measurement noise, we establish high-probability utility guarantees showing that corrected queries converge toward the
manifold at a non-asymptotic rate governed by sample size, noise level, bandwidth, and the
privacy budget. Simulations and case studies demonstrate accurate signal recovery under moderate
privacy budgets, illustrating clear utility-
privacy trade-offs and providing a deployable DP component for
manifold-based workflows in regulated environments without reengineering
privacy systems.
Read the full abstract ▾
Dynamical Systems
Characterization of Safe Stabilization and Control Lyapunov-Barrier Functions via Zubov Equation Formulation
Yiming Meng and Jun Liu
Design and analysis of stabilizing controllers with safety guarantees for nonlinear systems have received considerable
attention in recent years. Control Lyapunov-barrier functions (CLBFs) provide a powerful framework for simultaneously ensuring stability and safety; however, their construction for nonlinear systems remains challenging. To address this issue, we build on recent advances in PDE-based characterizations of control Lyapunov functions and Lyapunov-barrier functions for autonomous systems, and propose a succinct Zubov-HJB PDE formulation for safe stabilization of nonlinear control-affine systems under a common compatibility assumption. We further show that the viscosity solution of this PDE yields a maximal CLBF, enabling (not necessarily continuous) feedback synthesis with stability and safety guarantees. In light of recent advances in neural-network-based methods for solving Zubov-type PDEs, this theoretical framework also provides a natural interface to emerging numerical approaches.
Read the full abstract ▾
Geometric Topology
Cerf Diagrams and Hatcher-Wagoner Invariants for Barbell Maps
Xiayu Tan
For a half-unknotted implanted $(i,n-i)$-barbell $\beta=\beta_{i,n-i}$ in $M^n$, we construct two specific pseudo-isotopies, which we denote by standard barbell pseudo-isotopies, both resulting in that barbell diffeomorphism, each having a Cerf diagram only containing a single eye and with easily computable Hatcher-Wagoner invariants. We give an explicit formula for $\beta_{2,n-2}$ and a special class of $\beta_{3,n-3}$. Using this we show that for $n\geq 6$, every pseudo-isotopy with vanishing first Hatcher-Wagoner invariant can be isotoped to a composition of standard barbell pseudo-isotopies with $i=2$ or $3$. In dimension $n=4$, we further generalize the constructions and computations to half-unknotted immersed barbell diffeomorphisms and prove that for every $s\in \mathbb{Z}_2, \sigma\in \pi_2 M,\gamma\in \pi_1 M$ with $s=0 \text{ or }w_2^M(\sigma)\neq0$, there exists a standard immersed barbell pseudo-isotopy $f_\beta$ with the second induced Hatcher-Wagoner invariant $\Theta(f_\beta)=(s,\sigma)\cdot [\gamma]$.
Read the full abstract ▾
Probability
Infinite Horizon Optimal Control of Forward-Backward Stochastic Volterra Equations with Delay
Ibtissem Djaber, Hafiane Nawel and Samia Yakhlef
We consider an optimal control problem for infinite horizon systems governed by coupled forward-backward
stochastic Volterra integral equations with delay. Using Hida-Malliavin calculus, we prove both sufficient and necessary maximum principles for optimal control of such systems. We establish existence and uniqueness results for a class of infinite horizon backward
stochastic Volterra integral equations (BSVIEs).
Read the full abstract ▾
Optimization and Control · Cross-listed from eess.SY
Efstathios Iliakis, Wallace Gian Yion Tan, Liang Wu et al. (+2 more)
This paper develops a parametric Koopman operator framework for
Stochastic Model Predictive Control (SMPC), where the Koopman operator is parametrized by
Polynomial Chaos Expansions (PCEs). The model is learned from data using the Extended Dynamic Mode Decomposition – Dictionary Learning (EDMD-DL) method, which preserves the convex least-squares structure for the PCE coefficients of the EDMD
matrix. Unlike conventional
stochastic Galerkin projection approaches, we derive a condensed deterministic reformulation of the SMPC problem whose dimension scales only with the control horizon and input dimension, and is independent of both the lifted state dimension and the number of retained PCE terms. Our framework, therefore, enables efficient nonlinear SMPC problems with expectation and second-order moment constraints with standard convex optimization solvers. Numerical examples demonstrate the efficacy of our framework for uncertainty-aware SMPC of nonlinear systems.
Read the full abstract ▾
All authors Efstathios Iliakis, Wallace Gian Yion Tan, Liang Wu, Jan Drgona, Richard D. Braatz
History and Overview of Mathematics
On distance and proximity between Dummett and Brouwer
Mark van Atten
This paper asks what Brouwer might have replied to Dummett's interpretation of intuitionism. Complementing earlier literature, it treats Dummett's rejection of the ontological approach; the charge of psychologism and solipsism; indefinite extensibility; and predicativity. It is argued that Dummett's direct arguments against Brouwerian intuitionism do not settle the matter, and that, on the latter two themes,Dummett's position comes closer to Brouwer's than his own account suggests. The remaining philosophical distance, however, is substantial.
Read the full abstract ▾
Optimization and Control
Chvátal-Gomory Rounding of Eigenvector Inequalities for QCQPs
Santanu S. Dey, Nan Jiang, Aleksandr Kazachkov et al. (+2 more)
We introduce and analyze a class of valid inequalities for nonconvex quadratically constrained optimization problems (QCQPs) which we call Eigen-CG inequalities. These inequalities are obtained by applying a Chvátal-Gomory (CG) rounding to the well-known eigenvector inequalities for QCQPs, and transferring binary-valid inequalities to the continuous setting via a result of Burer and Letchford (2009). We define three nested subfamilies and prove that they are strictly contained in one another. However, we show that the convex conic closure of two of these subfamilies is equal and, in fact, coincides with the Boros-Hammer inequalities – a powerful family of inequalities that include, in particular, the triangle and McCormick inequalities. Using this CG perspective, we also prove that dense Eigen-CG inequalities are ineffective when used with the standard SDP+McCormick relaxation. This provides a complementary perspective on what is observed in practice: that sparse inequalities are impactful. Finally, based on these insights, we develop a computational strategy to find sparse Eigen-CG cuts and verify their effectiveness in nonconvex QCQP instances. Our results confirm that density quickly degrades effectiveness, but that including sparse inequalities beyond triangle inequalities can provide significant improvements in dual bounds.
Read the full abstract ▾
All authors Santanu S. Dey, Nan Jiang, Aleksandr Kazachkov, Andrea Lodi, Gonzalo Muñoz
Group Theory · Cross-listed from quant-ph
Two Problems on Quantum Computing in Finite Abelian Groups
Ulises Pastor-Díaz and José M. Tornero
In the context of finite Abelian groups two problems are presented and solved using
quantum computing techniques. The first is the well–known Hidden Subgroup Problem, originally solved by Simon in a landmark work. The second is the Fully Balanced Image Problem, originally introduced by the authors (joint with J. Ossorio–Castillo), which is related to a certain class of mappings (which contains strictly, for instance, the family of group morphisms). Both problems are tackled using a combination of two techniques: first, a conversion into Boolean objects, better suited for
quantum computing arguments, and subsequently a custom–tailored
algorithm which takes advantage of the Generalised Phase–Kick Back technique.
Read the full abstract ▾
Probability
Parisian ruin of locally self-similar Gaussian processes
Svyatoslav M. Novikov
We derive exact tail asymptotics of the Parisian ruin probability for Gaussian risk models driven by locally self-similar Gaussian processes with a power-type deterministic trend. The considered setting includes non-stationary Gaussian processes whose local correlation structure is governed by a self-similar limiting process, extending classical fractional Brownian motion models. The asymptotic behaviour is shown to depend on the interplay between the local variance decay, the self-similarity index, and the trend exponent, leading to several distinct regimes. In each regime, the ruin probability admits an explicit asymptotic representation involving Parisian Pickands-type constants. The analysis relies on a uniform Pickands lemma allowing for families of limiting Gaussian fields, extending existing double-sum techniques and enabling the treatment of locally self-similar Gaussian risk models.
Read the full abstract ▾
Numerical Analysis
Adaptive Polynomial Filtering for Hermitian Interior Eigenproblems: Convergence Analysis
Xiaofei Xu, Yuhui Ni, Shengguo Li et al. (+1 more)
Interior
eigenvalue problems for large-scale sparse Hermitian
matrices are fundamental in computational science. We propose an adaptive
polynomial filtering strategy based on Chebyshev expansion of a step function, integrated into a filtered subspace iteration framework. We establish pointwise convergence bounds in both undamped and damped settings and incorporate an enhanced spurious
eigenvalue detection technique to improve efficiency and robustness. At the implementation level, we employ MaSpMM to accelerate the
polynomial filtering step. Numerical results demonstrate the efficiency and robustness of the proposed method compared with classical approaches.
Read the full abstract ▾
All authors Xiaofei Xu, Yuhui Ni, Shengguo Li, Juan Zhang