Peer Revenue Play credits. Real papers.

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Friday 17 April

Probability

Extrapolation of max-stable random fields with Fréchet marginals

We propose a method for the prediction of stationary max–stable random fields with $\alpha$-Fréchet marginal distribution $H_\alpha$. The method is suitable to cope with heavy tails for $\alpha\in(0,2)$ and is (approximately) exact in marginal distributions. It is based on a recent extrapolation approach via level sets which requires no moment assumptions. An explicit connection between the excursion metric and the Davis-Resnick distance is established. The existence of the predictor is proven. The non-uniqueness of the forecast is demonstrated on several examples. The method is tested on multiple simulated time series and random fields as well as applied to real data of annual maximum precipitation.
Read the full abstract

Optimization and Control

Empirical Asymptotic Runtime Analysis of Linear Programming Algorithms

This paper takes an empirical look at asymptotic runtime growth rates for the most widely used algorithms for solving linear programming (LP) problems across a set of six optimization application areas that are known to produce large and difficult LP models. On the algorithm side, we consider the simplex method, interior-point methods, and PDHG. On the model side, we use a large language model (LLM) to create families of instances in different application areas, allowing us to study model types and sizes that are simultaneously synthetic and realistic. The results indicate that simple regression models typically predict observed runtimes quite well within a model class, and that asymptotic behavior can vary significantly between the different algorithms. This may have a significant impact on which algorithms will be most effective for solving large LP models in the future.
Read the full abstract

Combinatorics

Some results on small ordered and cyclic Ramsey numbers

Let $k \in \mathbb{N}$ and let $H_1, H_2, \ldots, H_k$ be simple graphs such that for each $j \in \{ 1, 2, \ldots, k \}$, the vertex set of $H_j$ is $\{ 0, 1, 2, \ldots, n_j - 1 \}$ for some $n_j \in \mathbb{N}$. The ordered Ramsey number $R_\mathrm{ord}(H_1, H_2, \ldots, H_k)$ is the smallest $n \in \mathbb{N}$ for which every $k$-edge-coloring of the complete graph on the vertex set $\{ 0, 1, 2, \ldots, n - 1 \}$ contains $H_j$ as a monochromatic subgraph of color $j$ for some $j \in \{ 1, 2, \ldots, k \}$, with the vertices appearing in the same order as in $H_j$. Inspired by the work of Poljak, we apply the Kissat SAT solver to determine new small two-color ordered Ramsey numbers of various classes of graphs: monotone paths, monotone cycles, alternating paths, stars, complete graphs and nested matchings. In addition, we introduce the cyclic Ramsey numbers $R_\mathrm{cyc}(H_1, H_2, \ldots, H_k)$ as a natural relaxation of the ordered Ramsey numbers, and once again use Kissat to determine various such numbers for the two-color case. By observing structural patterns in the computational results, we determine all ordered or cyclic Ramsey numbers for several pairs of classes of graphs. Furthermore, we obtain some bounds on ordered and cyclic Ramsey numbers where one argument is a connected graph, while the other is a monotone path or a monotone cycle. We also explore how reinforcement learning can be used through the recently developed Reinforcement Learning for Graph Theory (RLGT) framework to obtain lower bounds on ordered and cyclic Ramsey numbers. Finally, we introduce the permutational Ramsey numbers to show how the different Ramsey-type formulations involving standard, ordered and cyclic Ramsey numbers can be unified within a group-theoretic framework.
Read the full abstract

All authors Nino Bašić, Ivan Damnjanović, Dragan Stevanović, Ivan Stošić

Differential Geometry

Cones over minimal products cannot be calibrated by smooth calibrations

We extend a key result in [Zha26], by establishing the obstruction that the minimal product structure (for minimal submanifolds or stationary currents in spheres) automatically makes all cones over (non-trivial) minimal products fail to be calibrated by any global defined smooth calibration in Euclidean spaces.
Read the full abstract

Combinatorics · Cross-listed from cs.DM

Halfspace separation in geodesic convexity

Let $G = V, E$ be a simple connected undirected graph. A set $X \subseteq V$ is geodesically convex if for any pair of vertices $x, y \in X$, all vertices on all shortest paths in $G$ from $x$ to $y$ are contained in $X$. A set $H \subseteq V$ is said to be a {halfspace} if both $H$ and its complement (denoted by $H^c$) are convex. Given two sets $A, B \subseteq V$, the { halfspace separation} problem asks if there exist complementary halfspaces $H, H^c$ such that $A \subseteq H$ and $B \subseteq H^c$. The halfspace separation problem is known to be NP-complete for the geodesic convexity of general graphs. We show that geodesic halfspace separation is polynomial for weakly bridged graphs, pseudo-modular graphs, and the basis graphs of matroids.
Read the full abstract

Combinatorics

Extremal results for graphs with binding number strictly less than $1/r$

The binding number $b(G)$ of a graph, introduced by Woodall [J. Combin. Theory, Ser. B, 1973], is a central topic of both structural and extremal graph theory. It is closely related to fundamental combinatorial and structural properties of graphs. The graphs with $b(G)\geq1$ exhibit strong expansion properties and a highly connected global structure. In contrast, the structure for graphs with $b(G)<1$ remains far less well understood. Kane et al. [J. Graph Theory, 1981] proved that if $b(G)<1$, then every binding set of $G$ is independent. Goddard and Swart [Quaest. Math., 1990] showed that if $b(G)\leq1$, then the toughness $\tau(G)\leq b(G).$ This makes it particularly interesting to investigate extremal problems for graphs with \(b(G)<1\). For any integer $r\geq1,$ we completely characterize the unique extremal graph that maximizes the size (spectral radius) among all graphs of order $n$ satisfying $b(G)<\frac{1}{r}.$ For any bipartite graph $G=(X,Y)$ on $n$ vertices, it is readily seen that $b(G)\leq\min\{|X|/|Y|,|Y|/|X|\}\leq1.$ Notably, the complete balanced bipartite graph $K_{\frac{n}{2}, \frac{n}{2}}$ achieves the maximum size (spectral radius) among all bipartite graphs with $b(G)=1$. In this paper, we completely determine the extremal graphs maximizing the size or the spectral radius among all bipartite graphs with $b(G)<\frac{1}{r}$, where $r\geq1$ is an integer.
Read the full abstract

Group Theory

Generation of Generalised Wreath Products of Symmetric Groups

Let I be a finite partially ordered set and let (Sym({\Delta}i),{\Delta}i)i be a sequence of symmetric groups indexed by I. Construct the generalised wreath product (F, {\Delta}) on this sequence of permutation groups. We determine the minimum number d(F) of generators required for this generalised wreath product.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Characterizing all non-Hermitian degeneracies using algebraic approaches: Defectiveness and asymptotic behavior

The presence of degeneracies plays a crucial role in describing the behavior of non-Hermitian (NH) systems. In these systems, there are two key types of degeneracies: $n$-bolical degeneracies, which are analogous to Hermitian degeneracies, and various forms of exceptional points, each associated with different orders that correspond to sizes of the Jordan blocks. These types of degeneracies may coalesce at the same energy level, forming multi-block degeneracies. To understand how a multi-block degenerate NH system responds to perturbations, one should address how each types of involved degeneracies disperse. In this work, we systematically characterize the asymptotic behavior of all types of multi-block degeneracies in NH systems using a rigorous mathematical formulation. Through a range of examples, we demonstrate that our algebraic approach can facilitate the analysis of NH degeneracies in various settings relevant to experiments.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Converting non-Hermitian degeneracies of any order: Hierarchies of exceptional points and degeneracy manifolds

The emergence of various types of degeneracies plays a crucial role in optimizing and engineering different physical phenomena in non-Hermitian physics. In our work, we focus on the derogatory Exceptional Points (EPs), which are characterized by multiple Jordan blocks corresponding to the same eigenvalue. We demonstrate that, under certain infinitesimal perturbations, a derogatory EP can be converted into an EP of different structure without varying the total order of degeneracy. In particular, such conversion can increase the size of the largest Jordan block and, hence, the sensitivity of the eigenspectrum to parameter variation, which is an important feature for practical applications. Furthermore, by analyzing all possible conversions, we introduce hierarchies of degeneracies of the same order that appear when perturbing non-Hermitian systems. We systematically explore hierarchies in the absence of any symmetry and when pseudo-Hermitian symmetry is present. Our study facilitates engineering various degeneracies of non-Hermitian systems, paving the way to extending the implications of non-Hermitian physics.
Read the full abstract

Category Theory

Cells, convexity and contractibility in general categories

The two pillars of Algebraic topology - homology and homotopy theory rely on the availability of basic building blocks called cells. Cells take the form of simplexes, and have properties such as faces, sub-cells, convexity and contractibility. The first two cells, namely the line and point lead to the concept of homotopy. The collection of maps from the cells and the redundancies among them determine the homology of objects. This article presents a procedure by which such cells can be built in general categories satisfying some simple axioms. The cells satisfy the categorical analogs of convexity and contractibility. This enables a cellular theory for the general category, carrying notions of homotopy, homology, cellular approximation and homotopy equivalence which are mutually compatible in the same way as in the familiar context of Topology.
Read the full abstract

Dynamical Systems

Generic families of circle diffeomorphisms have many coexisting periodic orbits

We prove that for a generic family of circle diffeomorphisms every parameter value that corresponds to an irrational rotation number is approximated by parameter values for which the diffeomorphisms have arbitrarily large finite numbers of periodic orbits. This phenomenon implies that families where irrational rotation numbers appear are not weakly structurally stable. Moreover, we prove that any locally residual set of one-parameter families with nonconstant rotation number yields a continuum of weak equivalence classes of families.
Read the full abstract

Optimization and Control · Cross-listed from eess.SY

A numerical approach to the co-design of PID controllers and low-pass filters for time-delay systems

This paper addresses the numerical optimization of proportional-integral-derivative (PID) controllers for linear time-invariant systems with delays, where the derivative action is implemented using a low-pass filter. While performance assessment is often based on the spectral abscissa of the ideal PID-controlled system, the inclusion of a derivative filter fundamentally alters the closed-loop spectral properties and cannot be treated as a post-processing step. In particular, the spectral abscissa of the filtered closed-loop system may differ significantly from that of its unfiltered counterpart, potentially affecting both stability and performance. We propose a systematic numerical design framework in which the PID gains and the filter constant are optimized simultaneously by directly minimizing the spectral abscissa of the filtered closed-loop system. Treating the filter as an integral part of the control design allows us to reconcile robustness at high frequencies, in the sense of mitigating fragility issues due to approximate identities, with performance at low frequencies, in addition to counter measurement noise amplification. At the end of the presentation, numerical examples illustrate the proposed approach and highlight the benefits of controller-filter co-design. The results apply to general linear systems with input and/or state delays and are valid for both single-input single-output (SISO) and multi-input multi-output (MIMO) configurations.
Read the full abstract

History and Overview of Mathematics

Adolf Hurwitz and the Fundamental Theorem of Galois Theorie: The Königsberg Lectures of 1890-1891

In the winter semester of 1890–1891 Adolf Hurwitz delivered a lecture course at the Albertina University in Königsberg entitled -Theorie der algebraischen Gleichungen-. These lectures contain a particularly clear presentation of the ideas of Evariste Galois and, in particular, a proof of the fundamental theorem of Galois theory formulated in the language of substitutions. The present paper analyzes Hurwitz's treatment of this result on the basis of his lecture notes preserved in the ETH Library in Zurich (Hs 582:66), together with material from his Mathematisches Tagebuch 23 (Hs 582:23). After placing the Königsberg lectures in their historical context, we give an overview of their mathematical content and reconstruct in detail Hurwitz's argument leading to the fundamental theorem.
Read the full abstract

Numerical Analysis

Low-rank eigenvalue solvers for block-sparse matrix product states

We consider an iterative eigensolver for Schrödinger equations that constructs low-rank approximations of eigenfunctions with accuracy-adapted ranks, with particular focus on fermionic Schrödinger equations in second-quantized form and on matrix product state approximations enforcing particle number conservation. We provide a complete analysis of a solver based on preconditioned inverse iteration combined with rank truncation and propose a generalization to subspace iteration for the joint approximation of several eigenspaces. The practical performance of the method is illustrated by numerical tests for several model problems.
Read the full abstract

Numerical Analysis

Convergence of a Finite Volume Scheme for the Navier-Stokes-Korteweg Model via Dissipative Solutions

We propose a concept of dissipative weak (DW) solutions for the Navier-Stokes-Korteweg (NSK) system and prove conditional convergence of a structure-preserving finite volume scheme towards such a solution. DW solutions provide a generalized solution concept in computational fluid dynamics and have recently attracted significant attention. They provide an extension of the famous Lax Equivalence Theorem to nonlinear problems, i.e. consistency and stability of a numerical scheme imply convergence. Our work builds on recent advances where convergence towards DW solutions of structure-preserving schemes has been established for the Euler and Navier-Stokes equations. Indeed, we prove convergence of a recently proposed FV scheme by leveraging its conservation and dissipation properties as well as its consistency.
Read the full abstract

Information Theory

Decoding Algorithms for Tensor Codes

Tensor codes are a generalisation of matrix codes. Such codes are defined as subspaces of order-r tensors for which the ambient space is endowed with the tensor-rank as a metric. A class of these codes was introduced by Roth, who also outlined a decoding algorithm for low tensor-rank errors that can be generalised to an algorithm with exponential complexity in the decoding radius. They may be viewed as a generalisation of the well-known Delsarte-Gabidulin-Roth maximum rank distance codes. We study a generalised class of these codes. We investigate their properties and outline decoding techniques for different metrics that leverage their tensor structure. We first consider a fibre-wise decoding approach, as each fibre of a codeword corresponds to a Gabidulin codeword. We then give a generalisation of Loidreau-Overbeck's decoding method that corrects errors with properties constrained by the dimensions of the slice spaces and fibre spaces. The metrics we consider are bounded from above by the tensor-rank metric, and therefore these algorithms also decode tensor-rank weight errors.
Read the full abstract

Analysis of PDEs

A fractional De Giorgi isoperimetric type inequality

We establish an isoperimetric type inequality for the level sets of functions in fractional Sobolev spaces. This answers a question posed by the first author in a previous paper. To obtain it, we work out a slight modification of some estimates for nonlocal interaction functionals established by Savin and Valdinoci. We also show how said isoperimetric inequality leads to the Hölder continuity of functions in (weak) fractional De Giorgi classes.
Read the full abstract

Mathematical Physics · Cross-listed from cond-mat.stat-mech

Exact Steady State of a One-end Driven XXZ Spin Chain with Boundary Field

We find an exact nonequilibrium steady state of an open dissipatively driven XXZ spin-1/2 chain with source or sink spin bath at one end and an arbitrary boundary field at the other end.

Analysis of PDEs

Existence and regularity of solutions to parabolic-elliptic nonlinear systems

In this paper we study the existence and summability of the solutions to the following parabolic-elliptic system of partial differential equations with discontinuous coefficients: \begin{equation*} \begin{cases} u_t - \operatorname{div}(A(x, t) \nabla u) = -\operatorname{div}(u M(x) \nabla \psi) + f(x, t) & \text{in } \Omega_T, \\ -\operatorname{div}(M(x) \nabla \psi) = |u|^\theta & \text{in } \Omega_T, \\ \psi(x, t) = 0 & \text{on } \partial \Omega \times (0, T), \\ u(x, t) = 0 & \text{on } \partial \Omega \times (0, T), \\ u(x, 0) = 0 & \text{in } \Omega. \end{cases} \end{equation*} Here, $\Omega$ is an open and bounded subset of $\mathbb R^N$, $N>2$, $\theta\in(0,\frac{2}{N})$, $0<T<+\infty$ and $\Omega_T=\Omega\times(0,T)$. We prove existence results for data $f\in L^1(\Omega_T)$ and a corresponding increase in summability that obeys the $L^p$-regularity theorems for parabolic equations proved by Aronson-Serrin and by Boccardo-Dall'Aglio-Gallouët-Orsina. In particular, despite the term $u M(x)\nabla\psi$ not being regular enough (since it only belongs to $L^2(\Omega_T)$), the solution $u$ belongs to $L^s(\Omega_T)\cap L^q(0,T;W^{1, q}_0(\Omega))$ for suitable $s>1$ and $q>1$.
Read the full abstract

Differential Geometry

The Koopman–von Neumann–Landau–Ginzburg theory and a Proof of the Kontsevich–Soibelman Conjecture

We show that the Hilbert space of the Koopman–von Neumann formulation of Landau–Ginzburg theory is parametrised by a real Monge–Ampère domain, which carries a natural pre-Frobenius. Restricting to finite-dimensional (dually flat) exponential families, the parameter space becomes a Monge–Ampère domain and a pre-Frobenius manifold. Our main theorem proves that for every Berglund–Hübsch–Krawitz mirror pair of Calabi–Yau orbifolds arising from an invertible polynomial, this Monge–Ampère domain (the open probability simplex) is the base of a Lagrangian torus fibration on both the original and the mirror hypersurface, with dual fibres in the sense of Strominger–Yau–Zaslow. The construction recovers the SYZ picture from the Landau–Ginzburg–Koopman–von Neumann framework. In particular, this proves the Kontsevich–Soibelman conjecture (2001) for all Berglund–Hübsch–Krawitz mirror pairs: the base of the SYZ fibration is a Monge–Ampère domain (the open simplex), and the torus fibrations on the mirror pair are dual. A toy model of cones of positive definite matrices illustrates the geometric structures.
Read the full abstract

Combinatorics

Cluster topography

Using the LP algebraic toolkit, Conway's original topograph is rethought of as a cluster construction, paving the way for a wider topography based on mutation-type local rules. As a remarkable application of such cluster-driven upgrade, both the process of analytic continuation for Painlevé VI and the reduction algorithm for quadratic forms are endowed with the Laurent phenomenon. En passant, the rattlesnake is defined so to complete the bijection between snake graphs and rationals to the whole of $\mathbb{Q}$.
Read the full abstract

Differential Geometry

Foliated Geometry of Inverse Problems: Torsion, Curvature Duality, and Near-Associativity

We present a geometric framework for reconstruction problems based on Vaisman foliations and Atiyah–Molino sequences. Independent projections induce transverse foliations and dual connections; vanishing torsion and curvature duality guarantee unique, path-independent reconstruction, while obstructions yield non-associative quasigroupoids. Toric symmetry provides equivariant uniqueness. Applications to generative AI imputation and cryo-electron microscopy demonstrate the framework's practical power, unifying differential geometry with data-driven inverse problems.
Read the full abstract

Representation Theory

Wedderburn decomposition of the rational group algebras of $\operatorname{SL}_2(q)$ and $\operatorname{PSL}_2(q)$

In this article, we derive explicit combinatorial formulas, depending only on $q$, for the Wedderburn decomposition of the rational group algebras of the finite linear groups $\operatorname{SL}_2(q)$ and $\operatorname{PSL}_2(q)$. Furthermore, we also determine the number of pairwise non-isomorphic simple $\mathbb Q G$-modules of each possible dimension for $G$ being either $\operatorname{SL}_2(q)$ or $\operatorname{PSL}_2(q)$.
Read the full abstract

Geometric Topology

Volume Conjecture and quantum hyperbolic invariants: the figure eight knot complement

We compute the real part of the semi-classical limit of the sequence of quantum hyperbolic invariants (QHI) of the figure-eight knot complement $M$. We show that it is rigid, in the sense that it does not depend on the choice of holonomy representation of $M$, and it is either $0$ or equal to the hyperbolic volume of $M$ divided by $2\pi$, depending on a parity condition satisfied by logarithms of the holonomy eigenvalues on the canonical longitude, where the logarithms are parameters of the QHI of $M$. Along the way we also survey some relevant general features of the QHI.
Read the full abstract

Numerical Analysis

Towards Universal Convergence of Backward Error in Linear System Solvers

The quest for an algorithm that solves an $n\times n$ linear system in $O(n^2)$ time complexity, or $O(n^2 \text{poly}(1/\epsilon))$ when solving up to $\epsilon$ relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science. There are two predominant paradigms for measuring relative error: forward error (i.e., distance from the output to the optimum solution) and backward error (i.e., distance to the nearest problem solved by the output). In most prior studies, convergence of iterative linear system solvers is measured via various notions of forward error, and as a result, depends heavily on the conditioning of the input. Yet, the numerical analysis literature has long advocated for backward error as the more practically relevant notion of approximation. In this work, we show that – surprisingly – the classical and simple Richardson iteration incurs at most $1/k$ (relative) backward error after $k$ iterations on any positive semidefinite (PSD) linear system, irrespective of its condition number. This universal convergence rate implies an $O(n^2/\epsilon)$ complexity algorithm for solving a PSD linear system to $\epsilon$ backward error, and we establish similar or better complexity when using a variety of Krylov solvers beyond Richardson. Then, by directly minimizing backward error over a Krylov subspace, we attain an even faster $O(1/k^2)$ universal rate, and we turn this into an efficient algorithm, MINBERR, with complexity $O(n^2/\sqrt\epsilon)$. Finally, we extend this approach via normal equations to solving general linear systems in $O(n^2\log(n)/\epsilon)$ time complexity. We report strong numerical performance of our algorithms on benchmark problems.
Read the full abstract

Mathematical Physics

Identification of optimal history variables and corresponding hereditary laws in linear viscoelasticity

We develop an operator-theoretic formulation of hereditary constitutive models and characterize optimal finite-rank internal-variable approximations in the sense of Kolmogorov $N$-widths. The history operator is shown to be compact under natural assumptions on the relaxation kernel, thereby admitting optimal low-rank approximations. The resulting reduced models inherit thermodynamic consistency, stability, and provable approximation bounds. An analysis clarifies the structural relation between hereditary representations and internal-variable theories and provides a rigorous basis for reduced-order modeling in computational mechanics. Selected numerical examples showcase optimal convergence of approximations with respect to rank and sampling.
Read the full abstract

Information Theory · Cross-listed from eess.SP

A Novel Framework for Transmitter Privacy in Integrated Sensing and Communication

ISAC systems introduce new privacy risks because an unintended sensing node may exploit the shared radio waveform to infer transmitter-related information even when the communication payload remains secure. This paper investigates transmitter privacy, defined as limiting unauthorized inference of transmitter-related information through channel estimation, in a RIS-aided multi-antenna wireless system with a transmitter, a legitimate receiver, a malicious sensor, and a RIS. The malicious sensor is assumed to estimate the transmitter–sensor channel, and the resulting channel state information can then support unauthorized sensing, inference, or related signal processing. To mitigate this threat, we consider a privacy-oriented design in which the transmitter adopts superposition-based signaling with a message signal and transmit-side artificial noise, while the RIS shapes the propagation environment in a privacy-aware manner. The channel-estimation performance at the malicious sensor is first analyzed under imperfect prior knowledge, and both the true and predicted mean-square-error expressions are derived. Based on this analysis, we formulate a joint active–passive beamforming design problem that maximizes the malicious sensor's predicted channel-estimation error subject to a communication quality-of-service constraint, a transmit-power budget, and the unit-modulus constraints of the RIS. The resulting non-convex problem is handled through a numerically efficient alternating-optimization framework based on an augmented Lagrangian reformulation. Numerical results show that RIS-assisted propagation shaping can substantially degrade unauthorized channel estimation relative to the non-RIS case while preserving reliable communication, and further show that the privacy gains also improve a more direct sensing metric, namely the malicious sensor's angle-of-arrival estimation accuracy.
Read the full abstract

All authors Vaibhav Kumar, Ahmad Bazzi, Christina Pöpper, Marwa Chafii

Algebraic Geometry

Height 1 Group Schemes and Prismatic F-Gauges

We describe the prismatic F-gauge associated to a finite flat height one group scheme over a smooth variety of positive characteristic. As applications, we derive the description of the crystalline Dieudonné module of Berthelot-Breen-Messing in this case and recover results of Bragg-Olsson describing flat cohomology using a Hoobler-type sequence.
Read the full abstract

Optimization and Control

An exact algorithm for vehicle routing problems with temporal dependency constraints

Temporal dependencies between customer visits, such as synchronization constraints, pose a fundamental challenge in vehicle routing. These dependencies, which arise in applications such as home healthcare routing, aircraft scheduling, and technician routing, introduce inter-route constraints that make the resulting problems significantly harder to solve. We present an exact solution method for vehicle routing problems with temporal dependencies capable of handling all types of temporal dependencies studied in the literature, unlike most existing approaches that target specific subclasses. Our approach is based on a fragment-based formulation in which routes are represented as sequences of a new type of fragment, designed to handle temporal dependency constraints. This formulation is solved via a price-cut-and-enumerate algorithm that computes a lower bound using alternating column-and-row generation, obtains an initial upper bound, and iteratively refines both bounds through fragment enumeration and branch-and-cut, supported by several new classes of valid inequalities. Computational experiments show that our method significantly outperforms state-of-the-art benchmark methods and is able to solve previously intractable instances while covering a wider range of temporal dependencies.
Read the full abstract

Information Theory

VLSF Decoding with Reliability Guarantees over Correlated Noncoherent Fading Channels

This paper studies reliability-guaranteed decoding for variable-length stop-feedback (VLSF) codes over correlated noncoherent fading channels. The decoding rule is based on the evolution of the information density associated with a given channel input-output realization. Due to channel memory, exact evaluation of this information density is intractable. To enable constructive decoding, computable finite-blocklength lower and upper bounds on the information density that hold uniformly over time along each input-output sequence are derived. The lower bound enables a stopping-time analysis for VLSF decoding and has an operational meaning, while the upper bound provides a reference for the relaxation gap, which is explicitly characterized. As a concrete application, the Gauss-Markov fading channel with Gaussian signaling is considered to numerically investigate the stopping-time distribution and the impact of fading correlation on decoding performance.
Read the full abstract

All authors Guodong Sun, Samir M. Perlaza, Philippe Mary, Jean-Marie Gorce