2026-01-19 | | Total: 196
We study joint source-channel coding over Markov channels through the empirical coordination framework. More specifically, we aim at determining the empirical distributions of source and channel symbols that can be induced by a coding scheme. We consider strictly causal encoders that generate channel inputs, without access to the past channel states, henceforth driving the current Markov state evolution. Our main result is the single-letter inner and outer bounds of the set of achievable joint distributions, coordinating all the symbols in the network. To establish the inner bound, we introduce a new notion of typicality, the input-driven Markov typicality, and develop its fundamental properties. Contrary to the classical block-Markov coding schemes that rely on blockwise independence for discrete memoryless channels, our analysis directly exploits the Markov channel structure and improves beyond the independence-based arguments.
For an algebraically closed field K, let G be a finite abelian group of K-linear automorphisms of a finite-dimensional algebra A and AG is the associated skew group algebra. The author with S. Trepode and A. G. Chaio introduced the notion of a Galois semi-covering functor to study the irreducible morphisms over skew group algebras. In this paper, we establish a Galois semi-covering functor between the morphism categories as well as the functor categories over the algebras A and AG and prove that their Krull-Gabriel dimension are equal. This computation confirms Prests conjecture on the finiteness of Krull-Gabriel dimension and Schroers conjecture on its connection with the stable rank (the least stabilized radical power) over skew gentle algebras. Moreover, we determine all posible stable ranks for (skew) Brauer graph algebras.
We study the abelian sub-C*-algebra of the CAR algebra generated by the start and face opertors of Kitaev's toric code. We show that it is a C*-diagonal equivalent to the canonical diagonal of the CAR algebra.
To make DNA a suitable medium for archival data storage, it is essential to consider the decay process of the strands observed in DNA storage systems. This paper studies the decay process as a probabilistic noisy torn paper channel (TPC), which first corrupts the bits of the transmitted sequence in a probabilistic manner by substitutions, then breaks the sequence into a set of noisy unordered substrings. The present work devises coding schemes for the noisy TPC by embedding markers in the transmitted sequence. We investigate the use of static markers and markers connected to the data in the form of hash functions. These two tools have also been recently exploited to tackle the noiseless TPC. Simulations show that static markers excel at higher substitution probabilities, while data-dependent markers are superior at lower noise levels. Both approaches achieve reconstruction rates exceeding $99\%$ with no false decodings observed, primarily limited by computational resources.
An important part of the information theory folklore had been about the output statistics of codes that achieve the capacity and how the empirical distributions compare to the output distributions induced by the optimal input in the channel capacity problem. Results for a variety of such empirical output distributions of good codes have been known in the literature, such as the comparison of the output distribution of the code to the optimal output distribution in vanishing and non-vanishing error probability cases. Motivated by these, we aim to achieve similar results for the quantum codes that are used for classical communication, that is the setting in which the classical messages are communicated through quantum codewords that pass through a noisy quantum channel. We first show the uniqueness of the optimal output distribution, to be able to talk more concretely about the optimal output distribution. Then, we extend the vanishing error probability results to the quantum case, by using techniques that are close in spirit to the classical case. We also extend non-vanishing error probability results to the quantum case on block codes, by using the second-order converses for such codes based on hypercontractivity results for the quantum generalized depolarizing semi-groups.
In this paper, we establish global $C^{1,α}$-regularity for bounded generalized solutions of elliptic equations in divergence form with Musielak-Orlicz growth and subject to Dirichlet or Neumann boundary conditions. In fact, our findings extend and generalize several important regularity results in cases of special attention such as variable exponent spaces, Orlicz spaces, and some $(p,q)$ situations. We also point out new conditions in the analysis that focus on the interplay between non-standard growth conditions and the boundary behavior in such generalized examples.
Randomized algorithms in numerical linear algebra have proven to be effective in ameliorating issues of scalability when working with large matrices, efficiently producing accurate low-rank approximations. A key remaining challenge, however, is to efficiently assess the approximation accuracy of randomized methods without additional expensive matrix accesses. Recent work has addressed this issue by deriving fast leave-one-out error estimators for the randomized SVD and Nyström decomposition, enabling accurate error estimation with no additional matrix accesses. In this work, we extend the leave-one-out framework to the generalized Nyström decomposition, an approach that can be applied to general rectangular matrices. We do this by deriving three new leave-one-out error estimators and validating their effectiveness through numerical experiments.
Let $G$ be a locally compact abelian group with Haar measure $μ$. For integers $n \geq 2$ and $H \geq 2$ and for any $n$-tuples $\mathbf{u}_1,\ldots, \mathbf{u}_H \in \mathbf{N}^n$, there exist measurable subsets $A_1,\ldots, A_n$ of $G$ such that the $n$-tuple $\left( μ(hA_1),\ldots, μ(hA_n) \right)$ has the same relative order as the $n$-tuple $\mathbf{u}_h$ for all $h = 1,\ldots, H$. For integers $m_{i,h}$ for $i =1,\ldots, n-1$ and $h = 1,\ldots, H$, there are Lebesgue measurable sets $A_1,\ldots, A_n$ in $\mathbf{R}$ such that $μ(hA_{i+1}) - μ(hA_i) = m_{i,h}$ for all $i$ and $h$.
We show that semi-simplicial spaces that i) admit inner horn fillers up to homotopy and ii) possess units in a weak sense provide a viable model for $\infty$-categories. The existence of units can be expressed through various quasi-unitality conditions, and we compare the natural generalization of three such conditions found in the literature. This work is motivated by applications in Floer homotopy theory.
We study the problem of determining which integer polynomials divide Newman polynomials. In this vein, we first give results concerning the $8438$ known polynomials with Mahler measure less than $1.3$. We then exhibit a list of polynomials that divide no Newman polynomial. In particular, we show that a degree-10 polynomial of Mahler measure \text{approximately} 1.419404632 divides no Newman polynomial, thereby improving the best known upper bound for any universal constant $σ$, if it exists, such that every integer polynomial of Mahler measure less than $σ$ divides a Newman polynomial. Finally, letting $l(x)$ denote Lehmer's polynomial, we explicitly construct Newman polynomials divisible by $l(x)^2$ with degrees up to $150$, and show that no Newman polynomial is divisible by $l(x)^3$ up to degree $160$.
This article is concerned with tensor field tomography in a fairly general setting, that takes refraction, attenuation and time-dependence of tensor fields into account. The mathematical model is given by attenuated ray transforms of the fields along geodesic curves corresponding to a Riemannian metric that is defined by the index of refraction. The data are given at the boundary tangent bundle of the domain and it is well-known that they can be characterized as boundary data of a transport equation turning tensor field tomography into an inverse source problem. This way the adjoint of the forward mapping can be computed using the integral representation or, equivalently, associated to a dual transport equation. The article offers and proves two different representations for the adjoint mappings both in the dynamic and static case. The numerical implementation is demonstrated and evaluated for static fields using the damped Landweber method with Nesterov acceleration applied to both, the integral and PDE-based formulations. The transport equations are solved using a viscosity approximation. The error analysis reveals that the integral representation significantly outperforms PDE-based methods in terms of computational efficiency while achieving comparable reconstruction accuracy. The impact of noise and deviations from straight-line trajectories are investigated confirming improved accuracy if refraction is taken into account. We conclude that the inclusion of refraction to the forward model pays in spite of increased numerical cost.
We describe a genetic algorithm to find extreme examples in the arithmetic of dynamical systems. The algorithm is applied to four problems: small (non-zero) canonical heights, many rational preperiodic points, long rational cycles, and long rational tails. Data is provided for extreme examples generated for polynomials up to degree 13 and rational functions up to degree 5. This work significantly expands the known examples of extreme behavior for several of the conjectured behaviors in arithmetic dynamics and provides a foundation from which to begin a more advanced application of machine learning techniques in the creation of extreme examples for arithmetic dynamics.
We study the entanglement complexity of a system consisting of two simple-closed curves (self-avoiding polygons) that span a lattice tube, referred to as a 2SAP. 2SAPs are of interest as the first known model of confined ring polymers where the linking probability goes to 1 exponentially with the size of the system. Atapour et al proved this in 2010 by showing that all but exponentially few sufficiently large 2SAPs contain a pattern that guarantees the 2SAP is non-split, provided that the requisite pattern fits in the tube. This result was recently extended to all tubes sizes that admit non-trivial links. Here we develop and apply knot theory results to answer more general questions about the entanglement complexity of 2SAPs. We first extend the 1992 concept of a good measure of knot complexity to a good measure, $F$, of spanning-link complexity for $k$-component links. Using tangle products, we show, for example, that the more complex the prime knot decomposition of any component of a given link type, the greater its $F$-measure. We then prove that all but exponentially few size $m$ 2SAPs have $F$ complexity that grows at least linearly in $m$ as $m\to \infty$. We establish that good measures of knot complexity yield good measures of spanning-link complexity. We also establish conditions whereby more general link invariants can yield good measures. In particular, we establish that measures based on several classical invariants are good measures by our definition, eg bridge number or the number of $p$-colourings. Finally, we consider how the tube dimensions affect which links are embeddable as 2SAPs as well as geometric restrictions on the entanglement complexity of the embeddings. For example, we establish that there are two-component links that occur as 2SAPs in a given tube size only when one of the components is forced into a non-minimal bridge number conformation.
Fix two integers $1\leq d<e$. We study the birational geometry of a parameter space for pairs of homogeneous polynomials of degrees $d$ and $e$ in two variables (in which the higher degree polynomial is well defined only up to a multiple of the lower degree polynomial). We show that one can run the MMP on this space, and that it eventually contracts the resultant divisor.
We present a novel probabilistic approach for optimal path experimental design. In this approach a discrete path optimization problem is defined on a static navigation mesh, and trajectories are modeled as random variables governed by a parametric Markov policy. The discrete path optimization problem is then replaced with an equivalent stochastic optimization problem over the policy parameters, resulting in an optimal probability model that samples estimates of the optimal discrete path. This approach enables exploration of the utility function's distribution tail and treats the utility function of the design as a black box, making it applicable to linear and nonlinear inverse problems and beyond experimental design. Numerical verification and analysis are carried out by using a parameter identification problem widely used in model-based optimal experimental design.
We present a comonadic approach to pretorsion theories on semiexact categories, i.e. categories equipped with a closed ideal of null morphisms that admits all kernels and all cokernels. We first prove that bihereditary pretorsion theories are comonadic in a 2-dimensional sense over the 2-category of semiexact categories with naturally chosen 1-cells. We then extend the built pseudo-comonad to guarantee that all pretorsion theories are pseudo-coalgebras. But interestingly, not all pseudo-coalgebras are pretorsion theories. Rather, pseudo-coalgebras give a generalized notion of pretorsion theory.
We study the Dvoretzky covering problem for random covering sets driven by general Borel probability measures. As our main result, we solve the problem of covering analytic sets by random covering sets generated by arbitrary Borel probability measures on the real line. Prior to this work, a complete solution was not known for any singular measure. Our solution is potential theoretic and involves a generalisation of a notion of capacity in the work of Kahane, who solved the problem of covering compact sets in the classical setting where the random covering process is driven by the Lebesgue measure on the unit circle. One of our key innovations is a simple but powerful application of the Jankov-von Neumann uniformisation theorem, which we believe to have interest outside of this work. In addition, we determine the critical exponent for the covering problem for polynomially decreasing sequences $(cn^{-t})_n$ for random covering sets driven by Borel probability measures on $\mathbb{R}^d$. At exactly the critical exponent, the covering property generally depends on the constant $c>0$, and as an application of our main result, we determine the critical constant for random covering sets driven by natural measures on strongly separated self-conformal sets on the line. The critical constant depends on the multifractal structure of the average densities of the measure, and the result is new even for the simplest case of the Hausdorff measure on the Cantor set.
This paper introduces a new set of large-scale benchmark instances for the Capacitated Vehicle Routing Problem (CVRP). The proposed XL set extends existing benchmarks by covering instances with 1,000 to 10,000 customers and a wide range of structural characteristics, following established generation principles from prior CVRP studies. A computational study involving several state-of-the-art algorithms is conducted to provide initial best known solutions (BKSs) for the XL instances, which serve as a baseline for a community-driven BKS challenge launched on the CVRPLib website. The instances are made publicly available to support experimental evaluation and comparison of solution methods. Furthermore, additional computational analyses are reported to compare algorithmic performance on other existing CVRP benchmark instances.
This article is an exposition on some recent theoretical advances in learning latent structured models, with a primary focus on the fundamental roles that optimal transport distances play in the statistical theory. We aim at what may be the most critical and novel ingredient in this theory: the motivation, formulation, derivation and ramification of inverse bounds, a rich collection of structural inequalities for latent structured models which connect the space of distributions of unobserved structures of interest to the space of distributions for observed data. This theory is illustrated on classical mixture models, as well as the more modern hierarchical models that have been developed in Bayesian statistics, machine learning and related fields.
We study the classification of spaces of continuous functions $C(K)$ under positive linear maps. For infinite countable compacta, we show that whenever $C(K)$ and $C(L)$ are isomorphic, there exists an isomorphism $T:C(K)\to C(L)$ satisfying either $T\geq 0$ or $T^{-1}\geq 0$. We also prove that for any compact spaces $K$ and $L$, the existence of a positive embedding $T: C(K) \to C(L)$ implies that the Cantor-Bendixson height of $K$ does not exceed the height of $L$. Furthermore, we introduce a one-sided positive Banach-Mazur distance and obtain new estimates for both the classical and positive distances. Notably, we prove the exact formula $d_{BM}(C(ω^{ω^α}), C(ω^{ω^αn})) = n+\sqrt{(n-1)(n+3)}$.
This paper investigates the asymptotic behavior of stochastic recursive inclusions in the presence of non-zero, non-diminishing bias, a setting that frequently arises in zeroth-order optimization, stochastic approximation with iterate-dependent noise, and distributed learning with adversarial agents. The analysis is conducted through the lens of input-to-state stability of an associated differential inclusion, which serves as the continuous-time limit of the discrete recursion. We first establish that if the limiting differential inclusion is input-to-state stable and the iterates remain almost surely bounded, then the iterates converge almost surely to the neighborhood of desired equilibrium. We then provide a verifiable sufficient condition for almost sure boundedness by assuming that the underlying operator is single-valued and globally Lipschitz. Finally, we show that several zeroth-order variants of stochastic gradient naturally fit within this framework, and we demonstrate their input-to-state stability under standard conditions. Overall, the results provide a unified theoretical foundation for studying almost sure convergence of biased stochastic approximation schemes through the Input to State stability theory of differential inclusions.
We prove that any finite $δ$-index hypersurface $M$ in ${\mathbb R}^{n+1}$ with constant mean curvature must be minimal, provided - the volume growth of $M$ is sub-exponential; - the Ricci curvature of $M$ satisfies $\operatorname{Ric}_M\geq -\frac{4(1-δ)}{n-1}|A|^2g,$ where $A$ is the second fundamental form and $g$ is the metric on $M.$ In the second case, our result further implies that, in addition to being minimal, such an $M$ must be a hyperplane. Notice that, we do not have any restriction on the dimension and that the second result is new also in the case of finite index hypersurfaces ($δ=0$).
We prove rigidity results describing contextually-constrained maps defined on Grassmannians and manifolds of ordered independent line tuples in finite-dimensional vector or Hilbert spaces. One statement in the spirit of the Fundamental Theorem of Projective Geometry classifies maps between full Grassmannians of two $n$-dimensional Hilbert spaces, $n\ge 3$, preserving dimension and lattice operations for pairs with commuting orthogonal projections, as precisely those induced by semilinear injections unique up to scaling. In a different but related direction, denote the manifolds of ordered orthogonal (linearly-independent) $n$-tuples of lines in an $n$-dimensional Hilbert space $V$ by $\mathbb{F}^{\perp}(V)$ (respectively $\mathbb{F}(V)$) and, for partitions $π$ of the set $\{1..n\}$, call two tuples $π$-linked if the spans along $π$-blocks agree. A Wigner-style rigidity theorem proves that the symmetric maps $\mathbb{F}^{\perp}(\mathbb{C}^n)\to \mathbb{F}(\mathbb{C}^n)$, $n\ge 3$ respecting $π$-linkage are precisely those induced by semilinear injections, hence by linear or conjugate-linear maps if also assumed measurable. On the other hand, in the $\mathbb{F}(\mathbb{C}^n)$-defined analogue the only other possibility is a qualitatively new type of purely-contextual-global symmetry transforming a tuple $(\ell_i)_i$ of lines into $\left(\left(\bigoplus_{j\ne i}\ell_j\right)^{\perp}\right)_i$.
In this paper, we study the existence of solutions to a sweeping process in the presence of stochastic perturbations, where the moving set takes uniformly prox-regular values and varies continuously with respect to the Hausdorff distance, without smoothness assumptions. We consider several geometric assumptions and establish important relationships between them.
We address discrete-time consensus on the Euclidean unit sphere. For this purpose we consider a distributed algorithm comprising the iterative projection of a conical combination of neighboring states. Neighborhoods are represented by a strongly connected directed graph, and the conical combinations are represented by a (non-negative) weight matrix with a zero structure corresponding to the graph. A first result mirrors earlier results for gradient flows. Under the assumptions that each diagonal element of the weight matrix is more than $\sqrt{2}$ larger than the sum of the other elements in the corresponding row, the sphere dimension is greater or equal to 2, and the graph, as well as the weight matrix, is symmetric, we show that the algorithm comprises gradient ascent, stable fixed points are consensus points, and the set of initial points for which the algorithm converges to a non-consensus fixed point has measure zero. The second result is that for the unit circle and a strongly connected graph or for any unit sphere with dimension greater than or equal to $1$ and the complete graph, only for a measure zero set of weight matrices there are fixed points for the algorithm which do not have consensus or antipodal configurations.