Analysis of PDEs · Cross-listed from cs.LG
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Thursday 19 March
Uncertainty quantification for partial differential equations is traditionally grounded in discretization theory, where solution error is controlled via mesh/grid refinement. Physics-informed neural networks fundamentally depart from this paradigm: they approximate solutions by minimizing residual losses at collocation points, introducing new sources of error arising from optimization, sampling, representation, and overfitting. As a result, the generalization error in the solution space remains an open problem. Our main theoretical contribution establishes generalization bounds that connect residual control to solution-space error. We prove that when neural approximations lie in a compact subset of the solution space, vanishing residual error guarantees convergence to the true solution. We derive deterministic and probabilistic convergence results and provide certified generalization bounds translating residual, boundary, and initial errors into explicit solution error guarantees.
Analysis of PDEs
Remarks on Brunn-Minkowski-type inequalities related to the Ornstein-Uhlenbeck operator
We investigate Brunn-Minkowski-type inequalities for the torsional rigidity $T_\gamma$ and the first eigenvalue $\lambda_\gamma$ associated with the Ornstein-Uhlenbeck operator. Counterexamples are provided showing that neither concavity nor convexity properties hold for $T_\gamma$ on general bounded convex sets. We also demonstrate that log-concavity and log-convexity properties fail in this setting. In the case of centrally symmetric sets, we answer a question raised by Cordero-Erausquin and Eskenazis by showing that $T_\gamma^{1/(n+2)}$ is neither convex nor concave. On the positive side, we prove that $T_\gamma^{1/3}$ is convex with respect to Minkowski addition when restricted to Euclidean balls centered at the origin. For $\lambda_\gamma$, we answer negatively a question posed by Colesanti, Francini, Livshyts, and Salani by showing that the inequality $\lambda_\gamma(\Omega_t)^{-1/2} \geq (1-t)\lambda_\gamma(\Omega_0)^{-1/2} + t\lambda_\gamma(\Omega_1)^{-1/2}$ does not hold, even for centrally symmetric sets.
Read the full abstract
Mathematical Physics
Duality of generalized Maxwell theories as an equivalence in derived geometry
We propose a non-perturbative description of the moduli spaces encoding p-form generalized Maxwell theories in any dimension, using derived differential geometry. Our approach synthesizes the Batalin–Vilkovisky formalism with differential cohomology. Within this framework we formulate Dirac charge quantization and show how such charge-quantized moduli spaces exhibit abelian duality between generalized Maxwell theories of different types. We also describe the compactification of generalized Maxwell theories along closed Riemannian manifolds by computing the pushforward of the underlying sheaves of cochain complexes that model differential cohomology.
Read the full abstract
Optimization and Control
Fast and Effective Computation of Generalized Symmetric Matrix Factorization
In this paper, we study a nonconvex, nonsmooth, and non-Lipschitz generalized symmetric matrix factorization model that unifies a broad class of matrix factorization formulations arising in machine learning, image science, engineering, and related areas. We first establish two exactness properties. On the modeling side, we prove an exact penalty property showing that, under suitable conditions, the symmetry-inducing quadratic penalty enforces symmetry whenever the penalty parameter is sufficiently large but finite, thereby exactly recovering the associated symmetric formulation. On the algorithmic side, we introduce an auxiliary-variable splitting formulation and establish an exact relaxation relationship that rigorously links stationary points of the original objective function to those of a relaxed potential function. Building on these exactness properties, we propose an average-type nonmonotone alternating updating method (A-NAUM) based on the relaxed potential function. At each iteration, A-NAUM alternately updates the two factor blocks by (approximately) minimizing the potential function, while the auxiliary block is updated in closed form. To ensure the convergence and enhance practical performance, we further incorporate an average-type nonmonotone line search and show that it is well-defined under mild conditions. Moreover, based on the Kurdyka-Łojasiewicz property and its associated exponent, we establish global convergence of the entire sequence to a stationary point and derive convergence rate results. Finally, numerical experiments on real datasets demonstrate the efficiency of A-NAUM.
Read the full abstract
Differential Geometry
Hamiltonian Reduction in Affine Principal Bundles
This paper presents a Hamiltonian reduction procedure for field theories over affine principal bundles introducing a canonical identification to describe the reduced multisymplectic space without the introduction of a connection. The main goal is to provide a Hamiltonian analogue of the Lagrangian reduction theory developed in M. Castrillón López, P. M. Chacón, and P. L. García. J. Geom. Mech., 5(4):399-414, 2013. The core of this work lies in the derivation of this canonical identification, the reduced Hamilton-Cartan equations, and a reduced covariant bracket that describes the dynamics. Finally, this theoretical framework is illustrated with a fundamental example: molecular strands.
Read the full abstract
Numerical Analysis · Cross-listed from quant-ph
Quantum block encoding for one-pair semiseparable matrices
Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs $2\log(N)+7$ ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires $\mathcal{O}({\rm polylog} (N))$ time and has an error of $\mathcal{O}(N^2)$, where $N$ is the matrix size.
Read the full abstract
Operator Algebras
Spectral continuity of almost commutative manifolds for the $C^1$ topology on Riemannian metrics
Almost commutative models provide a framework for Connes' work on the standard model of particle physics. These models are constructed as products of a the canonical spectral triple of a compact connected spin manifold with a finite dimensional spectral triple. Motivated by the fundamental question of the dependence of the spectra of Dirac operators under change of metrics, we prove the continuity of the spectra of Dirac operators for almost commutative models as functions of the underlying Riemannian metric. We allow both the Riemannian metric (in the $C^1$ topology) and the Dirac operator of the finite-dimensional factor to vary simultaneously. Since the physics of the system is fundamentally encoded in this spectrum, this result is a form of stability result regarding the geometry, or physical, content of these models. This result is based upon a novel approach to prove continuity of spectra of Dirac operators using the spectral propinquity. Notably, this method provides a new, different proof of the classical results as well. To illustrate the versatility of our new method, we also apply our results to completely non-commutative family of examples, including quantum tori and quantum solenoids.
Read the full abstract
Representation Theory
The variety of Lie algebra representations
We study the affine variety $L_{n}(\mathfrak{g})$ of Lie algebra representations, the collection of all homomorphisms from an arbitrary $n$-dimensional Lie algebra into a fixed real semi-simple Lie algebra $\mathfrak{g}$. Using techniques from real Geometric Invariant Theory, we equip this variety with a natural moment map and associated energy functional arising from the action of the real reductive group $GL(n,\mathbb{R}) \times \text{Inn}(\mathfrak{g})$. We analyze the critical points of the energy functional and describe their structure. In particular, we prove that every semi-simple pair, that is representations of semi-simple Lie algebras, will globally minimize the energy in its orbit. As consequences, we obtain an elementary proof of the rigidity of semi-simple homomorphisms and derive a new proof of the Mostow theorem on the existence of compatible Cartan involutions for semi-simple subalgebras. Subsequent results concerning the structure of critical points of higher energy are also obtained.
Read the full abstract
Analysis of PDEs
A Variational Approach to Degenerate Monge–Ampère Equations with Mixed Measures and Monotonicity
We study the solvability and uniqueness for several degenerate Monge–Ampère equations including the Monge–Ampère eigenvalue problem in real Euclidean spaces that involve singular Borel measures. Our approach systematically analyzes the Monge–Ampère energy from the variational point of view and appropriately exploits monotonicity arguments. Our main tools consist of the mixed Monge–Ampère measure, Aleksandrov–Blocki–Jerison-type maximum principles, integration by parts, convex envelope, and comparison principles for subcritical equations. For the Monge–Ampère eigenvalue problem, we contrast the analysis within and without the energy class; even if it might not have solutions in the energy class, we show that the infimum of the Rayleigh quotient can be approximated from above by Monge–Ampère eigenvalues of the truncated measures, and by Rayleigh quotients of an inverse iterative scheme. We give examples showing that for very singular Borel measures, the Monge–Ampère eigenvalue problem has only solutions outside the energy class together with symmetry breaking and nonuniqueness.
Read the full abstract
Numerical Analysis
A stable and fast method for solving multibody scattering problems via the method of fundamental solutions
The paper describes a numerical method for solving acoustic multibody scattering problems in two and three dimensions. The idea is to compute a highly accurate approximation to the scattering operator for each body through a local computation, and then use these scattering matrices to form a global linear system. The resulting coefficient matrix is relatively well-conditioned, even for problems involving a very large number of scatterers. The linear system is amenable to iterative solvers, and can readily be accelerated via fast algorithms for the matrix-vector multiplication such as the fast multipole method. The key point of the work is that the local scattering matrices can be constructed using potentially ill-conditioned techniques such as the method of fundamental solutions (MFS), while still maintaining scalability and numerical stability of the global solver. The resulting algorithm is simple, as the MFS is far simpler to implement than alternative techniques based on discretizing boundary integral equations using Nyström or Galerkin.
Read the full abstract
Functional Analysis
Embeddings of variable Sobolev, Besov, and Triebel-Lizorkin spaces on metric measure spaces
Sobolev-type embeddings on metric measure spaces encode a subtle interaction between the analytic regularity of functions and the geometry of the underlying domain space. In this paper we develop an embedding theory for variable Hajłasz-type smoothness spaces on metric measure spaces whose “dimension” is allowed to vary pointwise through a bounded exponent $Q(\cdot)$ that governs a lower Ahlfors growth condition on the measure. We introduce variable exponent Hajłasz-Sobolev spaces $M^{s(\cdot),p(\cdot)}$, Hajłasz-Triebel-Lizorkin spaces $M^{s(\cdot)}_{p(\cdot),q(\cdot)}$, and Hajłasz-Besov spaces $N^{s(\cdot)}_{p(\cdot),q(\cdot)}$, and establish Sobolev, Morrey, and Moser-Trudinger type embeddings into variable exponent Lebesgue and Hölder spaces. These embeddings are proved both locally (on balls) under a lower Ahlfors $Q(\cdot)$-regularity condition on the measure and regularity assumptions on the exponents (notably log-Hölder continuity), and globally under additional geometric hypotheses such as geometric doubling and mild uniform bounds on the measure of unit balls. We also identify geometric conditions that are not only sufficient but, in appropriate forms, necessary for the validity of these embeddings, showing in particular that such inequalities force a lower growth bound on the measure of order $r^{Q(x)}$.
Read the full abstract
Numerical Analysis
Numerical Considerations for the Construction of Karhunen-Loève Expansions
This report examines numerical aspects of constructing Karhunen-Loève expansions (KLEs) for second-order stochastic processes. The KLE relies on the spectral decomposition of the covariance operator via the Fredholm integral equation of the second kind, which is then discretized on a computational grid, leading to an eigendecomposition task. We derive the algebraic equivalence between this Fredholm-based eigensolution and the singular value decomposition of the weight-scaled sample matrix, yielding consistent solutions for both model-based and data-driven KLE construction. Analytical eigensolutions for exponential and squared-exponential covariance kernels serve as reference benchmarks to assess numerical consistency and accuracy in 1D settings. The convergence of SVD-based eigenvalue estimates and of the empirical distributions of the KL coefficients to their theoretical $\mathcal{N}(0,1)$ target are characterized as a function of sample count. Higher-dimensional configurations include a two-dimensional irregular domain discretized by unstructured triangular meshes with two refinement levels, and a three-dimensional toroidal domain whose non-simply-connected topology motivates a comparison between Euclidean and shortest interior path distances between the grid points. The numerical results highlight the interplay between the discretization strategy, quadrature rule, and sample count, and their impact on the KLE results.
Read the full abstract
Optimization and Control
Stochastic Virtual Power Plant Dispatch via Temporally Aggregated Distributed Predictive Control with Performance Guarantees
This paper addresses the energy dispatch of a virtual power plant comprising renewable generation, energy storage, and thermal units under uncertainty in renewable output, energy prices, and energy demand. The nonlinear dynamics and multiple sources of uncertainty render traditional stochastic model predictive control (MPC) computationally intractable as the dispatch horizon, scenario set, and asset portfolio expand. To overcome this limitation, we propose a novel controller that seamlessly integrates MPC with time series aggregation and distributed optimization, simultaneously reducing the temporal, asset, and scenario dimensions of the problem. The resulting controller provides a rigorous performance guarantee through theoretically validated bounds on its approximation error, while leveraging dual information from previous MPC iterations to adaptively optimize the temporal aggregation. Numerical results show that the proposed controller reduces runtime by over 50% relative to traditional stochastic MPC and, crucially, restores tractability where the full-scale dispatch model proves intractable.
Read the full abstract
Analysis of PDEs
Well-posedness for the Navier-Stokes equations in Morrey spaces on non-compact manifolds
We analyze the incompressible Navier-Stokes equations on a class of non-compact Riemannian manifolds within the framework of Morrey spaces. Assuming bounded geometry together with negative Ricci and sectional curvature (e.g., hyperbolic spaces), we establish dispersive and smoothing estimates for the heat semigroups associated with the Beltrami, Bochner and Hodge Laplacians in Morrey spaces, as well as for the Riesz transform. In particular, the presence of negative curvature yields improved large-time decay compared to the Euclidean setting. These estimates are of independent interest and enable us to construct solutions in time-weighted spaces of Kato type, leading to local-in-time well-posedness on a broad class of non-compact manifolds and global one in the case of Einstein manifolds. In the latter setting, we assume a smallness condition on the initial data in Morrey norms, which are weaker than $L^{p}$-norms and thus allow for certain classes of large $L^{p}$-data. We also discuss extensions to Ricci-flat manifolds. Our results introduce a new class of non-decaying and rough initial data for the Navier-Stokes equations on manifolds, extending previous works in Lebesgue and Sobolev spaces.
Read the full abstract
Numerical Analysis
GLENN: Neural network-enhanced computation of Ginzburg-Landau energy minimizers
In this work, we propose a neural network-enhanced finite element strategy to compute the minimizer of the Ginzburg-Landau energy based on an unsupervised deep Ritz-type strategy. We treat the parameter $\kappa$ as a variable input parameter to obtain possible minimizers for a large range of $\kappa$-values. This allows for two possible strategies: 1) The neural network may be extensively trained to work as a stand-alone solver. 2) Neural network results are used as starting values for a subsequent classical iterative minimization procedure. The latter strategy particularly circumvents the missing reliability of the neural network-based approach. Numerical examples are presented that show the potential of the proposed strategy.
Read the full abstract
Numerical Analysis
Reduced order computation of 2D elastodynamic Green's functions in layered soil using a low-rank tensor approximation
The evaluation of elastodynamic Green's functions across numerous source-receiver locations, frequencies, and material properties, particularly in the context of parametric studies or boundary element computations, is computationally demanding and memory intensive. This paper presents a reduced order modeling strategy based on the Greedy Tucker Approximation (GTA), which incrementally constructs a low-rank representation of the Green's tensor through rank-one enrichments obtained via a Proper Generalized Decomposition (PGD)-type alternating least squares procedure. A Petrov-Galerkin formulation is employed to improve convergence and approximation accuracy. The resulting multi-dimensional tensor, expressed in terms of one-dimensional basis functions and a compact core, achieves substantial reductions in memory requirements. The methodology is demonstrated for two cases: a soil layer on rigid bedrock and a layered halfspace. Different separable dimensions are considered to capture various combinations of source and receiver configurations, frequencies, and material parameters. Results are validated against those obtained with the direct stiffness method and computation times and memory requirements are compared.
Read the full abstract
Dynamical Systems
Parametric Spectral Submanifolds across Hopf Bifurcations with Applications to Fluid Dynamics
We investigate the persistence and regularity of spectral submanifolds (SSMs) in high-dimensional parametric dynamical systems undergoing a Hopf bifurcation. By analyzing how resonances in the linearized spectrum near bifurcation points limit the existence and smoothness of SSMs, a phenomenon that has been mostly overlooked, we show that low-order Taylor coefficients of the SSM expansion and the associated reduced dynamics persist smoothly through the bifurcation. This analysis generalizes to any local bifurcation and provides a clear estimate of the parameter ranges over which a parametric SSM model can be justified, thus illustrating how globally the model can be extended despite the presence of resonances near criticality. We demonstrate these findings on multiple examples, including a data-driven SSM approach to the lid-driven cavity flow. For that problem, we construct a parametric SSM-reduced model that accurately captures the full transition to periodic dynamics and the critical Reynolds number. These results provide a mathematical foundation for robust data- and equation-driven model reduction of fluid flows across bifurcations, enabling an accurate prediction of nonlinear dynamics across critical parameter regimes.
Read the full abstract
Numerical Analysis
A conservative, discontinuous Galerkin, tracer transport scheme using compatible finite elements
This paper outlines a conservative transport scheme for scalar tracers within a compatible finite element model for geophysical fluid equations. Instead of using the advective transport equation for a mixing ratio, a conservative transport equation is solved for the tracer density of the mixing ratio multiplied by the dry density. This ensures mass conservation in the continuous equations, which can be preserved in the discrete equations with a discontinuous Galerkin transport scheme. Our method is designed to work for two placements of the mixing ratio in a Charney-Phillips vertical staggering: either co-located with the dry density or vertically staggered from it. The new scheme is designed to conserve the tracer density and ensure consistency by maintaining a constant mixing ratio. Additionally, a mass-conserving limiter is developed to ensure non-negativity in the co-located configuration. Tests with terminator toy chemistry and a moist rising bubble show the use of the new transport scheme with physics terms and its ability to accurately model mass conservation of moisture species in a dynamical core setup.
Read the full abstract
Statistics Theory
Finite-sample bounds for multi-output system identification
This paper presents uniform-in-time error bounds for regularized linear regression with vector-valued outputs and conditionally zero-mean subgaussian noise. By revisitileveraging self-normalized martingale arguments, we obtain bounds that apply directly to multi-output regression. These bounds are tighter and hold in more general settings than commonly used methods in finite-sample system identification. Furthermore, because of a novel treatment of the regularization bias, they are tighter even in the scalar-output case. The mild assumptions we use allow for unknown dependencies between regressors and past noise terms, typically induced by system dynamics or feedback mechanisms. Therefore, these novel bounds can be applied to many affine-in-parameter system identification problems, including the identification of a linear time-invariant system from full-state measurements. These results enable less conservative uncertainty quantification in learning-based control, which may significantly improve performance in safety-critical applications.
Read the full abstract
Probability
Quantifying the effect of noise perturbation for the stochastic Burgers equation with additive trace-class noise
We establish upper bounds for the weak and strong error resulting from a perturbation of the noise driving the stochastic Burgers equation, where we assume the noise to be additive and of trace class and the initial value to be sufficiently regular. More specifically, replacing the covariance operator of the driving noise $Q_1 \in \mathcal{L}_1(L^2)$ in the Burgers equation by a covariance operator $Q_2 \in \mathcal{L}_1(L^2)$ results in a weak error of $\mathcal{O}\big(\| (-A)^{-1^{-} } (Q_1-Q_2) \|_{\mathcal{L}_1(L^2)}\big)$ and a strong error of $\mathcal{O}\big(\big\| (-A)^{-1/2^{-}}\big|Q_1^{1/2} -Q_2^{1/2}\big| \big\|_{\mathcal{L}_2(L^2)}\big)$. Here $\|\cdot \|_{\mathcal{L}_1}$ is the trace class norm, $\|\cdot \|_{\mathcal{L}_2}$ is the Hilbert-Schmidt norm, and $A$ is the one-dimensional Dirichlet Laplacian that represents the leading term in the Burgers equation. In particular, our results provide upper bounds for the weak and strong error arising when approximating the trace class noise by finite-dimensional noise; the rates we obtain reflect the general philosophy that the weak convergence rate should be twice the strong rate.
Read the full abstract
Representation Theory
Pascal, Catalan, Motzkin triangles and tensor product multiplicities
The main purpose of this note is to provide an elementary discussion of some simple triangles of integer numbers in particular through their connections with representation theory of $sl_2$. The triangles under consideration are the Catalan triangle and the Motzkin triangle together with their generalisations that we introduce here. We advocate the point of view that these triangles are given by the well-known and classical Pascal rule starting from a well-chosen initial condition. We give an elementary derivation of the fact that the numbers in these triangles are multiplicities appearing in tensor products of $sl_2$-representations and that they are simply expressed as a difference of generalised binomial coefficients. We also take the opportunity to discuss the “sum of squares” phenomenon that happens in these triangles through the lense of representation theory.
Read the full abstract
Number Theory
Minimal Weierstrass models and regular models of hyperelliptic curves
Let $C$ be a hyperelliptic curve of genus $g\ge 2$ over a discrete valuation field $K$ with perfect residue field. We study the minimal Weierstrass models of $C$. When there is more than one such model, we find interesting properties on the minimal regular model and the canonical model of $C$. For curves of genus $2$, we characterize the existence of the stable reduction in terms of the minimal Weierstrass models. When there is more than one such model, we can compute the Euler factor of $\mathrm{Jac}(C)$ and a volume form of the Néron model of $\mathrm{Jac}(C)$, using two specific minimal Weierstrass models.
Read the full abstract
Numerical Analysis
Solving Maxwell's Equations with Mimetic Methods
We present a mimetic finite-difference approach for solving Maxwell's equations in one and two spatial dimensions. After introducing the governing equations and the classical Finite-Difference Time-Domain (FDTD) method, we describe mimetic operators that satisfy a discrete analogue of the extended Gauss divergence theorem and show how they lead to a compact, physically consistent formulation for computational electromagnetics. Two numerical examples are presented: a one-dimensional sinusoidal wave interacting with a lossy dielectric slab, and a two-dimensional Gaussian pulse with Uniaxial Perfectly Matched Layer (UPML) absorbing boundary conditions. All implementations use the Mimetic Operators Library Enhanced (MOLE).
Read the full abstract
Algebraic Geometry
The Simplicity of the Hodge Bundle
Optimization and Control
Preference-Based Optimisation for Integrated Design and Group Decision-Making
Conventional multi-objective optimisation approaches (e.g., MOO-CP or MIP) fail in group decision-making by aggregating heterogeneous objectives without a valid preference foundation, producing Pareto sets instead of a unique actionable decision. As only humans define objectives, preferences constitute the legitimate basis for decision-making. Accordingly, four conditions for complex design-decision systems are established: (1) Preference-Key - all objectives, constraints, and trade-offs are evaluated within a unified preference domain using valid preference function modelling (PFM); (2) Integration - feasible system performance (object capability) and acceptable actor preferences (subject desirability) coexist within a single design-decision space; (3) Association - actors freely specify individual preferences and weights, enabling consistent aggregation towards group-optimal decision-making; and (4) Uniqueness - the solver identifies a single best-fit solution with maximum aggregated preference. The ODESYS methodology, employing the IMAP solver, enables integrated multi-objective design optimisation and multi-criteria decision-making. Its extension within the ODESYS/FIVES formulation broadens applicability while achieving elegant simplicity, explicitly operationalising affine preference aggregation and preserving equivalence with validated ODESYS 1.0 results. By mapping system behaviour into a unified preference-performance domain, ODESYS/FIVES delivers a single best-fit solution, even for highly constrained problems, guaranteeing feasible and acceptable outcomes. Two applications demonstrate transformation of multi-objective optimisation into pure group decision-making, achieving a best-fit-for-common-purpose within socio-physical reach.
Read the full abstract
Analysis of PDEs
Second order estimates for equations with sums of Hessian operators on Hermitian manifolds
In this paper, we establish an a priori second-order estimate for admissible solutions satisfying a dynamic plurisubharmonic condition to equations involving sums of Hessian operators on compact Hermitian manifolds. The estimate is derived using a concavity inequality for complex sum-of-Hessian operators.
Read the full abstract
Numerical Analysis
Complexity bounds on neural networks for the solution of structured linear systems of equations
We derive upper bounds on the complexity of ReLU neural networks approximating the solution of a linear system given the matrix and the right-hand side. We focus on matrices which are symmetric positive definite and sparse, as they appear in the context of finite difference and finite element methods. For such matrices, we extend available results for the matrix inversion to the task of solving a linear system, where we leverage favorable properties of classical methods such as the modified Richardson and the conjugate gradient method. Our bounds on the number of layers and neurons are not only explicit with respect to the size of the matrices, but also with respect to their condition numbers.
Read the full abstract
Combinatorics
Supercritical Site Percolation on Regular Graphs
We consider site (vertex) percolation on $d$-regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergence of the “Erdős-Rényi component phenomenon" in the supercritical regime $p=\frac{1+\epsilon}{d-1}$: namely, the appearance of a unique giant component of order $n/d$ in the percolated subgraph, with all other components being of size $O(\log n)$. Our main results apply both to the $d$-dimensional hypercube and to pseudo-random graphs, and resolve two open questions in these cases. We further discuss differences (and similarities) between bond (edge) percolation setting and site percolation setting.
Read the full abstract
Optimization and Control
A heavy-ball type curve search method for smooth convexly constrained optimization
This paper addresses smooth convexly constrained optimization problems where the Euclidean projection onto the feasible set is computationally tractable. Although momentum techniques like Polyak's heavy-ball are known for accelerating optimization algorithms, their use in constrained settings remains limited due to challenges in preserving feasibility and ensuring convergence. We thus propose a heavy-ball-type method that extends to the constrained case a recently introduced curve-search globalization framework. The method attempts a momentum update and performs a curvilinear search to enforce an Armijo-type descent condition: when the momentum step is infeasible or unacceptable, the algorithm smoothly reverts to a feasible descent direction. We prove that the algorithm is well-defined and globally convergent to stationary points; the derivation of these results is nontrivial due to the use of a heavy-ball type direction in a constrained setting, where it may generate infeasible iterates. We discuss the incorporation of further mechanisms into the algorithm, including non-monotone curve search, spectral steplength selection and an adaptive momentum strategy. Numerical experiments on benchmark problems show the method is robust and competitive with the state-of-the-art.
Read the full abstract
Combinatorics
Linear and group identifying codes in Hamming Graphs
Codes are crucial in many areas of applications. Different types of codes are designed to meet specific needs, which makes them more effective and useful. Linear codes are extensively used in data storage systems. Identifying codes are essential for locating malfunctioning processors. To combine these benefits, researchers have looked into a type of code called linear identifying codes. These codes blend the error-correction abilities of linear codes with the fault-finding capabilities of identifying codes. Group codes are also highly regarded for their strong properties and reliable decoding methods. In our work, we introduce a new type of identifying code called group Identifying codes. These codes aim to bring together the best features of both Identifying codes and group codes, offering enhanced performance in fault detection and system reliability. In this paper, we establish limits on the smallest size of a group identifying code when \( G \) is an \( n \)-dimensional Hamming cube \( K_{m_1} \square K_{m_2} \square \dots \square K_{m_n} \). Additionally, we determine the smallest size of a linear identifying code in \( K_p^n \) for a prime \( p \) and \( n \geq 2 \). In [1], it was hypothesized that \( \gamma^{ID}(K_m^3) = m^2 \) for an integer \( m \geq 2 \). Although this conjecture was disproven in [2], we demonstrate that group identifying codes in \( K_m^3 \) for an integer \( m \geq 2 \) and linear identifying codes in \( K_p^3 \) for a prime \( p \) indeed fulfill this conjecture.