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)

Monday 6 April

Combinatorics

Counting geodesic paths in graphs

A geodesic is a shortest path which connects a pair of vertices of a graph G. In this paper we define the geodesic subpath number gpn(G) of a graph G as the number of geodesics in G. The number of subtrees and subpaths are already studied in literature, but they are both large quantities. Hence, the geodesic subpath number which is related to these quantities but smaller than both, seems worthy of investigation. We first consider extremal graphs with respect to the geodesic subpath number among all connected graphs on n vertices. This number is minimized by the so called geodetic graphs, i.e. graphs in which each pair of vertices is connected by precisely one geodesic. As for the graphs which maximize the geodesic subpath number, we provide an upper bound on gpn(G) in terms of n and we further consider several graph families which might have a large gpn(G). Yet, their value of gpn(G) still does not attain the established bound, so narrowing the gap remains as an open problem. We also consider the class of cactus graphs on n vertices and k cycles and among them characterize extremal graphs with respect to this new invariant.
Read the full abstract

All authors Martin Knor, Jelena Sedlar, Riste Škrekovski, Xiao-Dong Zhang

Combinatorics

On Semisymmetric Height and a Multidimensional Generalization of Weighted Catalan Numbers

Weighted Catalan numbers are a class of weighted sums over Dyck paths. Well-studied for their arithmetic properties and applications to enumerative combinatorics, these numbers were recently generalized to the setting of $k$-dimensional Catalan numbers for $k \geq 2$. In this paper, we introduce the $k$-dimensional semisymmetric weighted Catalan numbers ($k$-dimensional SSWCNs), an alternative $k$-dimensional generalization, along with their variant, the $k$-dimensional $u$-bounded semisymmetric weighted Catalan numbers ($k$-dimensional $u$-bounded SSWCNs). We define these two classes of numbers using the notion of semisymmetric height, a new statistic on points in $\mathbb{Z}^k_{\geq 0}$ motivated by geometric symmetries of $k$-dimensional analogs of Dyck paths and of the fundamental Weyl chamber of type $A_{k-1}$. For our main results, we prove the eventual periodicity of $k$-dimensional SSWCNs and their $u$-bounded variants modulo a suitable integer $m$, and we derive formulas for several classes of $k$-dimensional $u$-bounded SSWCNs. Additionally, using semisymmetric height, we derive novel analogs in the $k$-dimensional setting of the integer sequence counting Dyck paths by height and of the Narayana numbers. We conclude the paper with a future direction for generalizing weighted Catalan numbers to the $k$-dimensional setting.
Read the full abstract

Combinatorics

Measuring Depth of Matroids

Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursive depth parameters for matrices and matroids, aiming to unify recently introduced and scattered concepts. We propose a general framework that naturally yields eight different depth measures for matroids, prove their fundamental properties and relationships, and relate them to two established notions in the field: matroid branch-depth and matroid tree-depth (a natural depth counterpart of matroid tree-width). In particular, we show that six of our eight measures are mutually functionally inequivalent, and among these, one is functionally equivalent to matroid branch-depth and another to matroid tree-depth. We also prove that all these depth measures, possibly except one, coincide on matroids and on matrices over any field, which, perhaps surprisingly, is not a trivial finding. Finally, we provide a comparison between the matroid parameters and classical depth measures of graphs.
Read the full abstract

All authors Jakub Balabán, Petr Hliněný, Jan Jedelský, Kristýna Pekárková

Information Theory · Cross-listed from cs.DB

Query Optimization and Evaluation via Information Theory: A Tutorial

Database theory is exciting because it studies highly general and practically useful abstractions. Conjunctive query (CQ) evaluation is a prime example: it simultaneously generalizes graph pattern matching, constraint satisfaction, and statistical inference, among others. This generality is both the strength and the central challenge of the field. The query optimization and evaluation problem is fundamentally a "meta-algorithm" problem: given a query $Q$ and statistics $\cal S$ about the input database, how should one best answer $Q$? Because the problem is so general, it is often impossible for such a meta-algorithm to match the runtimes of specialized algorithms designed for a fixed query – or so it seemed. The past fifteen years have witnessed an exciting development in database theory: a general framework, called PANDA, that emerged from advances in database theory, constraint satisfaction problems (CSP), and graph algorithms, for evaluating conjunctive queries given input data statistics. The key idea is to derive information-theoretically tight upper bounds on the cardinalities of intermediate relations produced during query evaluation. These bounds determine the costs of query plans, and crucially, the query plans themselves are derived directly from the mathematical proof of the upper bound. This tight coupling of proof and algorithm is what makes PANDA both principled and powerful. Remarkably, this generic algorithm matches – and in some cases subsumes – the runtimes of specialized algorithms for the same problems, including algorithms that exploit fast matrix multiplication. This paper is a tutorial on the PANDA framework. We illustrate the key ideas through concrete examples, conveying the main intuitions behind the theory.
Read the full abstract

Optimization and Control

Muon Dynamics as a Spectral Wasserstein Flow

Gradient normalization can stabilize deep-learning optimization, and spectral normalizations are especially natural for matrix-shaped parameter blocks; Muon is the motivating example. We study an idealized deterministic, continuous-time, vanishing-momentum version of this idea in the mean-field regime, where wide models are represented by probability measures on parameter space. Starting from normalized matrix flows, we introduce Spectral Wasserstein distances indexed by norms $\gamma$ on positive semidefinite matrices: the trace norm recovers the classical $W_2$ distance, the operator norm gives the Muon geometry, and Schatten norms interpolate between them. We develop a static Kantorovich formulation, a max–min robust-cost representation, and Gaussian reductions extending the Bures formula. For monotone norms, we prove equivalence with a Benamou–Brenier formulation and obtain a gradient-flow interpretation of normalized mean-field training dynamics. Numerical experiments illustrate the resulting flows for MMD objectives, Gaussian reductions, two-layer ReLU models, and shallow attention.
Read the full abstract

Metric Geometry

An improved bound for sumsets of thick compact sets via the Shapley–Folkman theorem

Let $E_1,\dots,E_n \subset \mathbb{R}^d$ be compact sets of positive diameter with Feng–Wu thickness at least $c>0$. Feng and Wu proved that $E_1+\cdots+E_n$ has non-empty interior when $n>2^{11}c^{-3}+1$. We show that \[n>\frac{\sqrt d}{(\sqrt{1+c}-1)^2}=\frac{\sqrt d\,(\sqrt{1+c}+1)^2}{c^2}\] already suffices. In particular, since $0<c\le 1$, the bound $n>6\sqrt d\,c^{-2}$ is enough. For fixed dimension $d$, this improves the exponent in $c^{-1}$ from $3$ to $2$, while introducing only an explicit factor of $\sqrt d$. The proof replaces the one-summand-at-a-time enlargement of Feng–Wu by a simultaneous convexification step based on a radius form of the Shapley–Folkman theorem.
Read the full abstract

Probability

On a Problem of M. Kac on Laplace Distributions

We give counterexamples to a problem of M. Kac in the Scottish Book, which asks whether a certain nonlinear operation on two characteristic functions characterizes Laplace distributions, in analogy with the Cramér–Lévy theorem for Gaussian distributions. We then give an affirmative answer to a refined version of the problem. Finally, we develop a general framework for such characterization problems, construct generalized counterexamples, and pose some open questions.
Read the full abstract

Dynamical Systems

Unlikely intersections in families of polynomial skew products

Motivated by the study of unlikely intersection in the moduli space of rational maps, we initiate our investigation on algebraic dynamics for families of regular polynomial skew products in this article. Our goals are threefold. (1) We classify special loci – which contain a Zariski dense set of postcritically finite points – in the moduli space of quadratic regular polynomial skew products. More precisely, special loci include families of homogeneous polynomial endomorphisms, families of split endomorphisms, and polynomial endomorphisms of the form $(x^2,y^2+bx)$ up to conjugacy. As a consequence, we verify a special case of a conjecture proposed by Zhong. (2) Let $F_t$ be a family of regular polynomial skew products defined over a number field $K$ and let $P_t, Q_t\in K[t]\times K[t]$ be two initial marked points. We introduce a good height $h_{P_t}(t)$ which is built from the theory of adelic line bundles for quasi projective varieties. We show that the set of parameters $t_0\in \overline{K}$ for which $P_{t_0}$ and $Q_{t_0}$ are simultaneously $F_{t_0}$-preperiodic is infinite if and only if $h_{P_t}=h_{Q_t}$. (3) As an application of $h_{P_t}$, we show that, under some degree conditions of $P_t$, if there is an infinite set of parameters $t_0$ for which the marked point $P_{t_0}$ is preperiodic under $F_{t_0}$, then the Zariski closure of the forward orbit of $P_t$ lives in a proper subvariety of $\mathbb{P}^2$. As a by-product, we conditionally verify a special case of a conjecture of DeMarco–Mavraki which is a relative version of the Dynamical Manin–Mumford Conjecture.
Read the full abstract

Mathematical Physics · Cross-listed from gr-qc

The formation of a weak null singularity in the interior of generic rotating black holes

Given a characteristic initial value problem with smooth data representing a dynamical event horizon settling down to that of Kerr in the subextremal, strictly rotating range with suitable upper and lower bounds, we prove that a weak null singularity forms, across which the spacetime metric is continuously extendible but not Lipschitz extendible. The bulk of the proof is a stability argument showing that a dynamical Teukolsky field can be approximated by a linear Teukolsky field, whose linear instability was proved in previous works.
Read the full abstract

Probability · Cross-listed from physics.ao-ph

Tracing the origin of tropical North Atlantic Sargassum blooms to West Africa

We simulate the dynamics of pelagic Sargassum rafts as systems of finite-size floating particles, governed by a Maxey–Riley law with nonlinear elastic interactions. Using surface ocean currents and wind data from reanalysis systems for clump transport, we computed trajectories within a domain covering the tropical and subtropical north Atlantic. The subsequent motion is reduced using Ulam's discretization method into a time-inhomogeneous Markov chain that simulates a background Sargassum concentration. Bayesian inversion, combined with nonautonomous transition path theory, was used to infer the origin of the first significant recorded bloom in the tropical North Atlantic, which unfolded in April 2011. Both methodologies independently identified the bloom's origin as near the West African coast, up to two years before it was detectable via satellite imagery on the basin's western side. This finding supports anecdotal evidence of Sargassum strandings on the Ghanaian coast in 2009. Moreover, it correlates with unusual environmental conditions – such as increased nutrient loads from significant upwelling linked to a pronounced Dakar Niña and Saharan dust deposition – that promote bloom proliferation. Additionally, it aligns with the observation that the species of Sargassum in the 2011 bloom differ from those in the Sargasso Sea, which might otherwise be considered a natural origin.
Read the full abstract

All authors Francisco J. Beron-Vera, Maria J. Olascoaga, Phillipe Miron, Gage Bonner

Differential Geometry

On Duality, Legendre Bundles and Deformations

We introduce the Legendre bundle, a geometric structure encoding the essential duality of dually flat (Hessian) manifolds, and demonstrate that both exponential families in information geometry and a natural class of quantum field theories – which we term Hessian QFTs – arise as distinct realisations of this single framework. The Legendre bundle is shown to carry a canonical para-Kähler structure.
Read the full abstract

Analysis of PDEs

The entropy production is not always monotone in the space-homogeneous Boltzmann equation

We show an example of a function and a collision kernel for which the entropy production increases in time when we flow it by the space-homogeneous Boltzmann equation. The collision kernel is not any of the physically motivated kernels that are commonly used in the literature. In this particular setting, our result disproves a conjecture of McKean from 1966.
Read the full abstract

Optimization and Control

Curvature batching for integer and mixed-integer quadratic programming

We give an explicit algorithm for integer quadratic programming with running time $(nL)^{O(n^2)} \mathrm{poly}(\phi)$, where $n$ is the number of variables, $L$ bounds the absolute entries of the constraint and quadratic matrices, and $\phi$ is the total input encoding length. The linear objective and constraint right-hand sides enter only through $\phi$. The algorithm refines Lokshtanov's branching framework. Small integer kernel directions identify optima near constraint boundaries. When all chosen basis directions have nonnegative curvature, their gradient values can be imposed in one batch. The quadratic form then vanishes on the remaining kernel, and the residual problem is an integer linear program. Thus determinant growth after the batch does not feed into further branching. Over a polytope, the method extends to mixed-integer quadratic programming with $q$ continuous variables in time $(nL)^{O(n^2 (q+1)^2)} \mathrm{poly}(\phi)$, without a convexity assumption on the continuous block. We also decide and certify integer and mixed-integer unboundedness in $(m+n)^{O(n)} \mathrm{poly}(\phi)$ time for arbitrary rational polyhedra with $m$ inequalities. Noncopositivity on polyhedral cones and integer unboundedness are W[1]-hard in the dimension and admit no $(m+\phi)^{o(n)}$ algorithm under ETH, matching the linear order of dimension in the recession-test exponent. Companion results give a right-hand-side-independent bound for concave integer minimization and explicit runtimes for applications of IQP.
Read the full abstract

Number Theory

A note on Bremner's conjecture and uniformity

In 1998, Bremner conjectured that elliptic curves over the rationals having long sequences of distinct rational points whose $x$-coordinates are in arithmetic progression, have large rank. This was proved some years ago in a strong form as a consequence of previous work by the authors, by a combination of Nevanlinna theory and the uniform Mordell–Lang theorem of Gao–Ge–Kühne. Thus, if the ranks of elliptic curves over the rationals are uniformly bounded, then so are the lengths of the aforementioned arithmetic progressions. In this note we give a much more direct proof of this last statement, using the height-uniform Mordell theorem of Dimitrov–Gao–Habegger. The method is flexible and we give a new application of these ideas to $x$-coordinates in finitely generated multiplicative groups and geometric progressions; connections to a possible semiabelian uniform Mordell–Lang are also discussed.
Read the full abstract

Probability

Addendum to: Bounds for survival probabilities in supercritical Galton-Watson processes and applications to population genetics

In this addendum we extend Theorem 4.6 on the negative binomial distribution in `Bounds for survival probabilities in supercritical Galton-Watson processes and applications to population genetics' (Journal of Mathematical Biology 92:40, 2026; arXiv:2503.21403). We prove that the fractional linear lower bound to the negative binomial generating function derived there is indeed valid for every $x\in[0,1]$, and not only for $x\in[0,P^\infty_{\rm NB}]$, where $P^\infty_{\rm NB}$ is the extinction probability of the associated Galton-Watson process.
Read the full abstract

Combinatorics

On Generalized Token Graphs

The vertices of a $k$-token graph of a graph $G$ correspond to $k$ indistinguishable tokens placed on $k$ different vertices of $G$. Changing some conditions on both the nature of the tokens and the number of tokens allowed in each vertex of $G$, we define a generalization of token graphs, which we call generalized token graphs or simply supertoken graphs, which have different applications. Depending on the above conditions, different families of graphs (such as the Cartesian $k$-th power of $G$ by itself) are obtained, and we present some of their properties, including order, size, and connectivity.
Read the full abstract

All authors Xiaodi Song, Cristina Dalfó, Miquel Àngel Fiol, Mercè Mora, Shenggui Zhang

Optimization and Control · Cross-listed from cs.GT

Optimal Contest Beyond Convexity

In the contest design problem, there are $n$ strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that allocates a prize $p_i$ to the $i$-th rank based on the outcome, to incentivize contestants to exert higher costly efforts and induce high-quality outcomes. In this paper, we significantly deepen our understanding of optimal mechanisms under general settings by considering nonconvex objectives in contestants' qualities. Notably, our results accommodate the following objectives: (i) any convex combination of user welfare (motivated by recommender systems) and the average quality of contestants, and (ii) arbitrary posynomials over quality, both of which may neither be convex nor concave. In particular, these subsume classic measures such as social welfare, order statistics, and (inverse) S-shaped functions, which have received little or no attention in the contest literature to the best of our knowledge. Surprisingly, across all these regimes, we show that the optimal mechanism is highly structured: it allocates potentially higher prize to the first-ranked contestant, zero to the last-ranked one, and equal prizes to the all intermediate contestants, i.e., $p_1 \ge p_2 = \ldots = p_{n-1} \ge p_n = 0$. Thanks to the structural characterization, we obtain a fully polynomial-time approximation scheme given a value oracle. Our technical results rely on Schur-convexity of Bernstein basis polynomial-weighted functions, total positivity and variation diminishing property. En route to our results, we obtain a surprising reduction from a structured high-dimensional nonconvex optimization to a single-dimensional optimization by connecting the shape of the gradient sequences of the objective function to the number of transition points in optimum, which might be of independent interest.
Read the full abstract

Probability

Bounding the Gap Between Zeros of the Variable- Parameter Confluent Hypergeometric Function

This paper derives a lower bound on the spacing between adjacent zeros of the confluent hypergeometric function $\Phi(a,b,z)$ when $a$ is variable and $(b,z) \in \mathbb{R}^+$ are known and fixed. Monotonicity of the bound is established, and the results are used to assess the accuracy of asymptotic approximations for the first passage probability of a Wiener process.
Read the full abstract

Operator Algebras

On Relative Invariant Subalgebra Rigidity Property

A countable discrete group $\Gamma$ is said to have the relative ISR-property if for every non-trivial normal subgroup $N\trianglelefteq\Gamma$ and every von Neumann subalgebra $\mathcal{M}\subseteq L(\Gamma)$ invariant under conjugation by $N$, one has $\mathcal{M}=L(K)$ for some subgroup $K\le\Gamma$. Similarly, $\Gamma$ has the relative $C^*$-ISR-property if every $N$-invariant unital $C^*$-subalgebra $\mathcal{A} \subseteq C_r^*(\Gamma)$ is of the form $C_r^*(K)$. We show that every torsion-free acylindrically hyperbolic group with trivial amenable radical satisfies the relative ISR property. Moreover, we also show that all torsion-free hyperbolic groups have the relative $C^*$-ISR property. Furthermore, we establish an analogous relative ISR-property for irreducible lattices in higher-rank semisimple Lie groups, such as $\mathrm{SL}_d(\mathbb{Z})$ ($d \geq 3$), with trivial center.
Read the full abstract

Number Theory · Cross-listed from cs.CR

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol, valued for its low multiplicative complexity in Multi-Party Computation (MPC) and Zero-Knowledge Proof (ZKP) protocols. While its security over prime fields $\mathbb{F}_p$ is well-documented, recent interest has shifted toward instantiations over extension fields $\mathbb{F}_{p^r}$. This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $\mathbb{F}_{p^r}$. First, we analyze polynomial input encoding under a standard passive threat model (sequential additive counter queries). We demonstrate that while the absence of polynomial carry-overs causes an asynchronous "no-carry fracture" that neutralizes classical sliding-window collision attacks, the fracture itself is deterministically periodic. By introducing a novel "Differential Signature" bucketing technique, we prove that an adversary can systematically group fractured sequences by their structural shapes to bypass this defense, recovering the secret key in $\mathcal{O}(U \cdot p^r/M)$ operations, where $U$ is the unicity distance. Second, we evaluate the PRF under an active Chosen-Query threat model. We demonstrate that an adversary can circumvent the additive fracture by evaluating the PRF along a geometric sequence generated by a primitive polynomial. This structure invokes strict multiplicative homomorphism over $\mathbb{F}^*_{p^r}$, permitting a direct generalization of state-of-the-art table collision attacks to extract the key in $\mathcal{O}(p^r/M)$ operations. Finally, we establish the cryptographic boundaries of these attacks, formally proving the necessity of higher-degree key variants ($d \ge 2$) to achieve exponential security against structural reduction in extension fields.
Read the full abstract

Logic · Cross-listed from cs.CC

Failure of the strong feasible disjunction property

A propositional proof system $P$ has the strong feasible disjunction property iff there is a constant $c \geq 1$ such that whenever $P$ admits a size $s$ proof of $\bigvee_i \alpha_i$ with no two $\alpha_i$ sharing an atom then one of $\alpha_i$ has a $P$-proof of size $\le s^c$. We combine the work of Ilango (2025) and Ren et al. (2025) with the gadget proof complexity generator of K. (2007) and rule out the property for strong enough proof systems under the following two hypotheses: - there exists a language in class E that requires exponential size circuits even if they are allowed to query an NP oracle, - there exists a P/poly demi-bit in the sense of Rudich (1997).
Read the full abstract

Combinatorics

Hall-Littlewood-positive harmonic functionals on the algebra of symmetric functions

We study the problem of describing the set of real functionals on the quotient $\textrm{Sym}/(p_2-1)$ of the ring of symmetric functions that are nonnegative on the images of certain modified Hall-Littlewood symmetric functions. This question is equivalent to the problem, posed in [Adv Math 395, p.108087 (2022)], of describing the set of coadjoint-invariant measures for unitary groups over a finite field in the infinite-dimensional setting. Our main results constitute partial progress towards this problem. Firstly, we show that the desired set of functionals is very large, in the sense that it contains explicit families of examples depending on infinitely many parameters. Secondly, we provide an analogue of Kerov's mixing construction that produces new sought after functionals from known old ones. This construction depends on an explicit "$p_2$-twisted action" of $\textrm{Sym}$ on itself and the resulting dual map that makes $\textrm{Sym}$ into a comodule. Finally, our third main result explains the relation between the $p_2$-twisted comultiplication and the usual comultiplication on $\textrm{Sym}$.
Read the full abstract

Probability

Rapid convergence of tempering chains to multimodal Gibbs measures

We study the spectral gaps of parallel and simulated tempering chains targeting multimodal Gibbs measures. In particular, we consider chains constructed from Metropolis random walks that preserve the Gibbs distributions at a sequence of harmonically spaced temperatures. We prove that their spectral gaps admit polynomial lower bounds of order $11$ and $12$ in terms of the low target temperature. The analysis applies to a broad class of potentials, beyond mixture models, without requiring explicit structural information on the energy landscape. The main idea is to decompose the state space and construct a Lyapunov function based on a suitably perturbed potential, which allows us to establish lower bounds on the local spectral gaps.
Read the full abstract

Analysis of PDEs

Boundary estimates for parabolic non-divergence equations in $C^1$ domains

We obtain boundary nondegeneracy and regularity estimates for solutions to non-divergence form parabolic equations in parabolic $C^1$ domains, providing explicit moduli of continuity. Our results extend the classical Hopf-Oleinik lemma and boundary Lipschitz regularity for domains with $C^{1,\mathrm{Dini}}$ boundaries, while also recovering the known $C^{1-\varepsilon}$ regularity for parabolic Lipschitz domains, unifying both regimes with a single proof.
Read the full abstract

Quantum Algebra

Drinfeld-Xu bialgebroid 2-cocycles twist the antipode

Ping Xu generalized Drinfeld 2-cocycles from bialgebras to associative bialgebroids over noncommutative base algebras. Any counital Drinfeld–Xu 2-cocycle twists the base algebra of the bialgebroid and a comultiplication on the total algebra, obtaining a new, twisted bialgebroid. Antipodes for bialgebroids have been considered, but finding a general way to twist the antipode, which is straightforward in the Hopf algebra case, appeared somewhat elusive. In this article, we prove that if an invertible antipode $S$ for the original bialgebroid exists, and another expression $V_F$ depending on the 2-cocycle $F$ is invertible, then the expected conjugation formula $S_F(-) = V_F^{-1} S(-) V_F$ indeed produces an invertible antipode $S_F$ for the twisted bialgebroid.
Read the full abstract

Information Theory

Partially deterministic sampling for compressed sensing with denoising guarantees

We study compressed sensing when the sampling vectors are chosen from the rows of a unitary matrix. In the literature, these sampling vectors are typically chosen randomly; the use of randomness has enabled major empirical and theoretical advances in the field. However, in practice there are often certain crucial sampling vectors, in which case practitioners will depart from the theory and sample such rows deterministically. In this work, we derive an optimized sampling scheme for Bernoulli selectors which naturally combines random and deterministic selection of rows, thus rigorously deciding which rows should be sampled deterministically. This sampling scheme provides measurable improvements in image compressed sensing for both generative and sparse priors when compared to with-replacement and without-replacement sampling schemes, as we show with theoretical results and numerical experiments. Additionally, our theoretical guarantees feature improved sample complexity bounds compared to previous works, and novel denoising guarantees in this setting.
Read the full abstract

Optimization and Control

Feasibility-Aware Imitation Learning for Benders Decomposition

Mixed-integer optimization problems arise in a wide range of control applications. Benders decomposition is a widely used algorithm for solving such problems by decomposing them into a mixed-integer master problem and a continuous subproblem. A key computational bottleneck is the repeated solution of increasingly complex master problems across iterations. In this paper, we propose a feasibility-aware imitation learning framework that predicts the values of the integer variables of the master problem at each iteration while accounting for feasibility with respect to constraints governing admissible integer assignments and the accumulated Benders feasibility cuts. The agent is trained using a two-stage procedure that combines behavioral cloning with a feasibility-based logit adjustment to bias predictions toward assignments that satisfy the evolving cut set. The agent is deployed within an agent-based Benders decomposition framework that combines explicit feasibility checks with a time-limited solver computation of a valid lower bound. The proposed approach retains finite convergence properties, as the lower bound is certified at each iteration. Application to a prototypical case study shows that the proposed method improves solution time relative to existing imitation learning approaches for accelerating Benders decomposition, while preserving solution accuracy.
Read the full abstract

All authors Bernard T. Agyeman, Zhe Li, Ilias Mitrai, Prodromos Daoutidis

Classical Analysis and ODEs

On a $_2F_1\big(\frac{1}{4}\big)$-identity due to Gosper

It is only in exceptional cases that a $_2F_1(z)$-series with rational parameters and a rational argument, apart from the cases for $z \in \{ \pm 1, \frac{1}{2} \}$ associated with classical hypergeometric identities, admits an evaluation given by a combination of $\Gamma$-values with rational arguments. In this paper, we present a new and integration-based approach toward the construction of special values for $_2F_1$-series of the desired form. We apply this approach using a $_2F_1\big(\frac{1}{4}\big)$-identity originally due to Gosper and later considered by Vidunas, Ebisu, and Zudilin, to evaluate a ${}_{2}F_{1}$-series of convergence rate $\big(\frac{172872}{185039}\big)^2$. With regard to extant research on so-called “strange” ${}_{2}F_{1}$-evaluations, as in the work of Ebisu and Zeilberger, our new series seems to have the largest numerator/denominator in its argument.
Read the full abstract

Optimization and Control

Sample Complexity for Markov Decision Processes and Stochastic Optimal Control with Static Risk Measures

We present an elementary state augmentation method for a class of static risk measure applied to the total cost for both Markov decision processes (MDPs) and stochastic optimal control (SOC), such that dynamic programming equations can be derived on the augmented space. Through this we discuss the sample complexities of these two problem classes. We demonstrate the application of the proposed approach by developing a general framework for studying risk-averse MDPs and SOCs with distributionally robust functional generated by $\phi$-divergences, and obtain new sample complexity results for commonly used divergence functions.
Read the full abstract

Commutative Algebra

An infinite series of Gorenstein local algebras failing the affine homogeneity property

We provide an infinite series of commutative finite-dimensional Gorenstein local algebras $A_n$ for $n \ge 2$. We give an elementary proof that the maximal ideal of every algebra $A_n$ possesses a one-dimensional subspace that is different from the socle and invariant under the automorphism group of $A_n$. The latter implies that the algebras $A_n$ fail the affine homogeneity property. We also discuss some consequences concerning additive actions on projective hypersurfaces, related to the generalized Hassett-Tschinkel correspondence for these algebras.
Read the full abstract