Peer Revenue Past citations are no guarantee of future returns

Papers

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

Mathematics

math Watch Mathematics (sign in to use)

Saturday 9 May

Information Theory

Tight Lower Bounds on The Single-Error Detection Threshold for Analog Error-Correcting Codes

Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of $k$ and $n$ for which every linear $[n, k]$ code $\mathcal{C}$ over $\mathbb{R}$ satisfies: $$\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}$$ Here, for any $\boldsymbol{x}\in\mathbb{R}^n$, $\mathsf{h}_1(\boldsymbol{x})$ represents the ratio between the largest and second largest absolute values of $\boldsymbol{x}$'s entries. As the simplest special case of Problem 1 (with $n-k=2$), the following problem was posed as Problem 2 in [1]: "Must every $(n-2)$-dimensional subspace of $\mathbb{R}^n$, $n$ even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least $(n/2)-1$?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary $n-k$ and Problem 2 corresponds to $n-k=2$. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where $n-k$ divides $k$. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.
Read the full abstract

All authors Zhengyi Jiang, Wenhao Liu, Zhongyi Huang, Bo Bai, Gong Zhang, Hanxu Hou

Algebraic Geometry

Refined obstructions to local-global principles for 0-cycles

We introduce new `refined' obstructions to local-global principles for 0-cycles on algebraic varieties over number fields. Assuming finiteness of relevant Tate–Shafarevich groups, we show that the Hasse principle and weak approximation for 0-cycles on generalised Kummer varieties and bielliptic surfaces are controlled by obstructions of this new type. As an additional application of our refined obstructions, we answer a question of Zhang about the relationship between the Brauer–Manin and connected descent obstructions for 0-cycles. We also show that a Corwin–Schlank style refined obstruction set coincides with the set of global 0-cycles, conditionally on the Section Conjecture.
Read the full abstract

All authors Francesca Balestrieri, Anouk Greven, Rachel Newton, Soumya Sankar, Katerina Santicola, Manoy Trip

Symplectic Geometry

Proper modules over Ginzburg dg algebras and compact Fukaya categories of plumbings

We study Ginzburg dg algebras which appear at the intersection of representation theory and symplectic topology. First, we provide a collection of proper modules that generates all proper modules over a Ginzburg dg algebra, without assuming the Jacobi-finite condition. Using this generation result, we study the immersed compact Fukaya category of a general plumbing space. In particular, we prove a generation result for the compact Fukaya category and show that it is equivalent to the category of proper modules over the wrapped Fukaya category, and hence to the category of microlocal sheaves on the Lagrangian skeleton.
Read the full abstract

Combinatorics

Proofs of four generating function conjectures for arbor polytopes

This paper proves four conjectured generating series, due to Chapoton, which concern invariants of posets and polytopes associated with a specific sequence of arbors. Two of these conjectures provide closed-form formulas for the generating series of the Zeta polynomial and the generating series of the M-triangle of the poset, respectively. The remaining two conjectures pertain, respectively, to the Ehrhart polynomial and the Laplace transform of the volume function of the associated arbor polytope.
Read the full abstract

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

Condensation Transition in Entropy-Constrained Probability Spaces

Probability spaces are known to undergo a concentration of measure in high dimensions. In particular, if a $K$-dimensional probability distribution is sampled from a $(K-1)$-dimensional simplex with uniform measure, with high probability its empirical distribution of components is logarithmic. Here, we extend this result to the subset of distributions populating level sets of de simplex defined by a fixed Shannon entropy $H_0$. We show that the empirical distribution of components of the large majority of sampled distributions undergoes a phase transition. A critical entropy $H_c \approx \log K - 1 + \gamma $ exists, below which the overwhelming majority of sampled distributions are found in a condensed state, in which a single component captures a macroscopic fraction of the total probability, while the remaining components form a homogeneous incompressible fluid background. We derive the magnitude of the critical entropy, as well as the empirical distribution of components both above and below threshold. These results provide insight into how the level sets of fixed entropy in the simplex are populated.
Read the full abstract

All authors Bautista Arenaza, Sebastián Risau-Gusman, Inés Samengo, Damián G. Hernández

Numerical Analysis

A Primer on the Karhunen-Loève Expansion

This article provides a primer on the spectral representation of random fields via the Karhunen-Loève Expansion (KLE). The goal is to bridge the gap between the theoretical foundations of the KLE and its application in computational modeling under uncertainty. We detail how tools from operator theory and probability are combined to analyze the convergence and optimality of the KLE. We also emphasize the associated computational and mathematical modeling considerations.
Read the full abstract

Dynamical Systems

Cyclicity of centers on center manifolds in a 3D chaotic system with a four-wing attractor

In this work, we investigate the conditions that guarantee the existence of centers on the center manifold, arising from Hopf points, in the new three-dimensional quadratic chaotic system introduced by B. Khaled et al. in 2024 in the Int. J. Data Netw. Sci. For some of the Hopf points of the system, we solve the center-focus problem on the center manifold, analyzing both its isochronicity and cyclicity. Our results significantly improve the previously known lower bound on the number of limit cycles bifurcating from Hopf points in this system, as established by B. M. Mohammed in 2025 in the Int. J. Bifurc. Chaos Appl. Sci. Eng.
Read the full abstract

Optimization and Control

Learning Generative Dynamics with Soft Path-Law Constraints: A McKean-Vlasov FBSDE Approach

We introduce a unified framework for learning stochastic dynamics from distributional observations and discretely observed trajectories. The key contribution is to combine soft law constraints, which regularize fitting to empirical distributions, with path-dependent supervision, which captures temporal structure that marginal distributions alone cannot identify. We formulate the problem as a discrete path-dependent McKean-Vlasov control problem, penalizing endpoint, intermediate marginal, and joint sampled-path laws within a single objective. Its optimality system takes the form of a McKean-Vlasov forward-backward stochastic differential equation (FBSDE), in which the marginal terms act continuously in time while the path-law term instead induces conditional adjoint jumps at the observation dates. We derive the reduced FBSDE for quadratic control cost and constant diffusion, establish local well-posedness for a Maximum Mean Discrepancy (MMD) path-law formulation, and develop a sample-based neural solver with causal representations. Experiments on synthetic transport, latent face transport, and human motion validate the framework. In particular, a two-state AMASS experiment under path-law supervision captures both low-to-high and high-to-low transitions, which marginal supervision alone cannot distinguish.
Read the full abstract

All authors Samer El Boustany, Samy Mekkaoui, Yadh Hafsi, Alexandre Alouadi, Huyên Pham

Combinatorics

Effective resistance and spanning trees in complete graphs with distance-class deletions

In this paper, we consider circulant graphs obtained from the complete graph $K_N$ by deleting all edges belonging to a prescribed distance class. We study, in a unified manner, the effective resistance, the expected hitting time, the number of spanning trees, and the number of two-component spanning forests of these graphs. For general distance-class deletions, these quantities admit natural spectral representations in terms of the Laplacian eigenvalues. However, such representations typically remain at the level of finite Fourier sums, and concise closed forms are not expected in general. We focus on the case of a single deleted distance class. When the number of vertices $N$ is odd and $\gcd(r,N)=1$, the graph $G_{N,r}$ is isomorphic to $G_{N,1}$. In this setting, we derive explicit exponential-type formulas for the effective resistance and the number of spanning trees, and obtain corresponding closed expressions for two-component spanning forests and expected hitting times. Our results show that the case $r=2$ is not essentially new, but follows from a general isomorphism structure underlying distance-class deletions. We also clarify the relation of our formulas to earlier results on the complete graph with a Hamiltonian cycle removed, and provide a unified derivation within a spectral framework. Moreover, by asymptotic analysis, we show that the ratio $\tau(G_{N,1})/\tau(K_N)$ converges to $e^{-2}$ as $N \to \infty$.
Read the full abstract

Rings and Algebras

Factor systems and geometric structures of strongly graded rings

Graded rings provide a natural algebraic framework for encoding symmetry via decompositions into homogeneous components indexed by a group, together with multiplication rules reflecting the group operation. Among graded rings, strongly graded rings form a particularly well-behaved and structurally rich class. In this paper we introduce a notion of factor systems for strongly graded rings, consisting of algebraic data that encode both the bimodule structure of the homogeneous components and their multiplication relations. In particular, this framework makes it possible to carry out explicit computations. We show that strongly graded rings with fixed principal component are classified, up to isomorphism, by conjugacy classes of such factor systems. Conversely, every abstract factor system gives rise to a strongly graded ring realizing it. In this way, the global structure of a strongly graded ring can be reconstructed from algebraic data on the principal component together with the grading group. Factor systems also provide a convenient framework for studying the problem of lifting derivations from the principal component to graded derivations of the whole ring. We derive explicit compatibility conditions for the existence of such lifts and interpret the resulting obstruction in cohomological terms. This leads to an algebraic analogue of the Atiyah sequence for strongly graded rings and to curvature-type invariants measuring the failure of graded lifts to form Lie algebra homomorphisms. The theory is illustrated by Leavitt path algebras.
Read the full abstract

Numerical Analysis · Cross-listed from cs.CE

Diffusion Restore: Real-Time Markov Chain Monte Carlo Light Transport

We present Diffusion Restore, a real-time framework for diffusion-based MCMC light transport. MCMC methods are highly suitable for sampling from complex high-dimensional distributions and for approximating integrals over them. In practice, they are often the only viable solution when direct sampling is not possible and alternative methods are either inefficient or cannot be applied due to the structure of the target distribution. However, controlling the exploration of the target distribution in MCMC methods remains challenging. Efficient exploration requires a balance between local exploration and global discovery, and local dynamics must rapidly explore individual modes without getting stuck or exhibiting excessive backtracking. The problem of global discovery has recently been addressed by the introduction of the Restore framework. In this work, we build on this framework and focus on improving local exploration. We show how to choose diffusion-based local dynamics within the Restore framework while completely avoiding Metropolis-adjustment, which is known to slow down convergence. Furthermore, we model these dynamics as nonreversible, introducing momentum in the drift and thereby enabling more directed exploration of the target distribution compared to reversible, random-walk-like dynamics. We provide a theoretical justification for the validity of our choice of local dynamics. Empirically, we demonstrate across diverse scenes that Diffusion Restore outperforms all existing MCMC light transport methods and establishes a new state of the art. In addition, we present a GPU implementation in ray tracing and compute shaders and achieve real-time frame rates. This demonstrates that Diffusion Restore is not only superior in offline rendering, but also outperforms traditional Path Tracing methods in real-time rendering settings, such as interactive applications and games.
Read the full abstract

Differential Geometry

An Upper Bound for Discrete Isometric Filling of Cycles

We study the discrete graph-metric analogue of Gromov's filling area problem for the cycle graph \(C_n\). An abstract triangulation \(K\) is an isometric filling of \(C_n\) if \(\partial K=C_n\) and the graph distance between any two boundary vertices is not shortened inside the \(1\)-skeleton of \(K\). Let \(D(n;\epsilon)\) denote the minimum number of vertices in a \((1-\epsilon)\)-Lipschitz filling of \(C_n\), and set \[ D^*=\liminf_{\epsilon\to0^+}\liminf_{n\to\infty}\frac{D(n;\epsilon)}{n^2}. \] Previous work gives the general lower bound \(D^*\ge 1/8\), while discretizing the hemisphere gives the upper bound \[ D^*\le \frac{1}{\pi\sqrt3}. \] In this paper we give an explicit discrete construction which improves the hemispherical upper bound. More precisely, we construct isometric fillings \(K_n\) of \(C_n\) with \[ |V(K_n)|\le \left(\frac16+o(1)\right)n^2, \] and hence \[ D^*\le \frac16<\frac{1}{\pi\sqrt3}. \] This can directly illustrate the discrete filling area problem is a proper relaxation of Gromov's original filling area problem and cannot be used to settle Gromov's conjecture. The construction is a concentric annular filling.
Read the full abstract

Optimization and Control

Efficient sparse GP-MPC with accurate mean and variance propagation applied for quadcopter flight control

This paper presents a computationally efficient approach for Gaussian process model predictive control (GP-MPC), where Gaussian process (GP) regression is used to complement a baseline model of the system dynamics. The proposed method achieves propagation of both the predicted mean and variance, thereby significantly reducing conservativeness compared with existing GP-MPC formulations. The nonlinear GP-MPC problem is reformulated into an exact linear parameter-varying (LPV) structure that preserves the nonlinear prediction dynamics in affine form without introducing further approximation. Moreover, closed-form derivations of moment matching (MM) predictions for sparse GPs are developed, including both mean and variance propagation under uncertain inputs, which improves scalability to larger datasets. This further enables recasting the resulting GP-MPC problem as a sequence of quadratic programs (QPs), which can be solved efficiently. The proposed framework significantly improves runtime efficiency while maintaining prediction accuracy, as demonstrated through simulation and real-world experiments on a Crazyflie 2.1 micro quadcopter.
Read the full abstract

General Topology

On GSI2-convergence in T0-spaces

In this paper,we introduce the concept of GSI$_2$-convergence in $T_0$ spaces and the related concept of (strongly) QI$_2$-continuous spaces. It is proved that if GSI$_2$-convergence in $X$ is topological iff $X$ is strongly QI$_2$-continuous for any irreducible complete $T_0$ space $X$.
Read the full abstract

Number Theory

Multiple integral representations of the Catalan's constant

In this paper, we present several novel integral representations of Catalan's constant. We begin by deriving an initial result expressed as a double integral. Subsequently, as a consequence of this result, we establish a general theorem that enables the representation of Catalan's constant in terms of a single integral. Finally, we provide a multiple integral representation of Catalan's constant in dimensions greater than or equal to two using the Lerch function. The results are accompanied by illustrative examples.
Read the full abstract

Group Theory

The Pascal matrix in the multivariate Riordan group

We generalize the concept of Pascal matrices to matrices associated with sets of points by considering multidimensional binomial coefficients as entries. We study their properties and prove that the infinite matrix associated with the set vectors with integral coordinates is in fact an element of the multivariate Riordan group.
Read the full abstract

Differential Geometry

Rigidity and gap theorems for Ricci shrinkers

We prove local versions of the Ricci curvature and $\nu$-entropy gap theorems for Ricci shrinkers, which respectively generalize a previous result of Munteanu-Wang and a prior result of the authors with Ma. The key point is that these local gaps depend only on the dimension and not on the global entropy or any other geometric information of the Ricci shrinker. As an application, we provide a local criterion for removable Type~I singularities of the Ricci flow.
Read the full abstract

Numerical Analysis

Non-Uniqueness of Solutions in Neural Variational Methods

Recent work has shown that strong-form physics-informed neural networks (PINNs) based on pointwise enforcement of differential operators can be ill-posed due to the combination of sufficiently expressive neural network trial spaces with finitely many measurements. In this work, we develop an abstract analytical framework that isolates this finite-information mechanism and extends its applicability beyond strong-form formulations. We apply the framework to three representative variational neural discretizations: the Deep Ritz method, neural network discretizations of variational regularization functionals, and weak PINNs. Despite their differing formulations, these methods constrain the neural trial function only through finitely many linear measurements, such as quadrature evaluations or finite-dimensional test spaces. We show that this structural feature leads to ill-posed discrete optimization problems, manifested by non-uniqueness or degeneracy of minimizers, independently of the well-posedness of the underlying continuous variational problem.
Read the full abstract

Optimization and Control

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

Large-scale machine learning models are trained on clusters of machines that exhibit heterogeneous performance due to hardware variability, network delays, and system-level instabilities. In such environments, time complexity rather than iteration complexity becomes the relevant performance metric for optimization algorithms. Recent work by Tyurin and Richtárik (2023) established the first time complexity analysis for parallel first-order stochastic optimization, proposing Rennala SGD as a time-optimal method for smooth nonconvex optimization. However, Rennala SGD is fundamentally a modification of SGD, and variance reduction techniques are known to improve the iteration complexity of SGD. In this work, we investigate whether variance reduction can also improve time complexity in heterogeneous systems. We show that, under a mean-squared smoothness assumption, variance reduction can improve time complexity in relevant parameter regimes. To this end, we propose Rennala MVR, a variance-reduced extension of Rennala SGD based on momentum-based variance reduction, and analyze its oracle and time complexity. We establish lower bounds for time complexity under these assumptions. On a stochastic quadratic benchmark, experiments with the exact method support the theory, while neural-network experiments with a practical inexact variant show similar empirical gains over Rennala SGD.
Read the full abstract

Algebraic Topology · Cross-listed from cs.LG

TopoGeoScore: A Self-Supervised Source-Only Geometric Framework for OOD Checkpoint Selection

Out-of-distribution (OOD) robustness is difficult to diagnose when target-domain labels are unavailable. We consider a more restrictive source-only variant of unsupervised accuracy estimation: selecting robust checkpoints using only source-domain representations, with no target samples or target labels. We propose TopoGeoScore, a source-only geometric scorer for label-free OOD checkpoint selection. Given a trained checkpoint, we construct class-conditional mutual $k$-nearest-neighbour graphs from source embeddings and extract three interpretable signals: a torsion-inspired reduced Laplacian log-determinant for global class-manifold complexity, Ollivier–Ricci curvature for local neighbourhood regularity, and higher-order topological summaries for fragmented connectivity, loops, and global–local inconsistency. Instead of fixing their weights by hand, TopoGeoScore learns a non-negative linear score through a self-supervised objective that enforces invariance under approximately geometry-preserving embedding views and separation from structure-breaking views. The score remains interpretable and uses no target-domain samples or labels. Results across CIFAR-based corruption and distribution-shift benchmarks, ImageNet-C, MNLI$\to$HANS transfer, and OGBN-Arxiv suggest that source representations contain measurable global–local–topological evidence of robustness, supporting practical checkpoint selection before deployment under distribution shift.
Read the full abstract

Category Theory

The singularity category of a separable extension

We prove that separable extensions of noetherian rings and finite étale morphisms of noetherian schemes give rise to separable extensions of singularity categories.

Mathematical Physics

Picard-Lefschetz theory and alien calculus: a case study

We compare Picard–Lefschetz theory and resurgence in three basic one-dimensional exponential integrals: the Airy model, the Bessel model, and the Gamma model. On the Picard–Lefschetz side, we describe the Lefschetz thimbles and compute the connecting trajectories between critical points appearing at Stokes phases. On the resurgent side, we analyze the Borel singularities of the saddle expansions and use alien operators to recover the same Stokes coefficients. These examples serve as explicit finite-dimensional test cases for the dictionary between thimble wall-crossing and alien calculus.
Read the full abstract

Optimization and Control · Cross-listed from stat.ML

Tight Generalization Bounds for Noiseless Inverse Optimization

Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context–action data. We study noiseless IO, where demonstrations are generated by a ground-truth objective. We provide a high-probability ${O}(\frac{d}{T})$ generalization bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset. We strengthen this guarantee under additional conditions that ensure uniqueness of the chosen action, bringing our IO guarantees in line with best-arm identification results in the bandit literature. We further show that the ${O}(\frac{d}{T})$ rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret. Notably, the resulting regret lower bound matches the corresponding upper bounds in the adversarial setting, indicating that the stochastic IO setting is effectively adversarial for the class of estimators studied here. Finally, we propose a parameter-free algorithm with lower per-iteration complexity than generic solvers. Experiments validate the predicted rates and illustrate the tightness of our bounds.
Read the full abstract

All authors Pouria Fatemi, Hoomaan Maskan, Suvrit Sra, Peyman Mohajerin Esfahani

Number Theory

Some Omega results for Dirichlet $L$-functions

Motivated by the first author's earlier work in 2024, we use the resonance method to establish some Omega results for Dirichlet $L$-functions, extending the previous results.

Statistics Theory · Cross-listed from cs.LG

Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation

We study online estimation in latent-variable models by recasting the problem as tracking a moving empirical equilibrium. Standard online EM and stochastic approximation analyses primarily study convergence toward the population parameter and typically do not isolate the empirical batch optimum from the online tracking error at finite horizon. Our framework decomposes the online estimate into the frozen batch equilibrium at the current running statistic and a tracking lag that captures the algorithm's delay behind this moving target. We prove a batch-to-online transfer theorem: provided $\lVert e_T \rVert_{L^{2}} = o(T^{-1/2})$, the online estimator inherits the batch central limit theorem and the sharp first-order risk constant. Our key observation is that the empirical optimum evolves on a smooth equilibrium manifold indexed by the running statistic. An $m$-th order equilibrium-jet predictor combined with an order-$\nu$ frozen corrector yields localized tracking rates $O(T^{-\nu(m+1)})$. We formalize EM-compressibility and EM-jet$^R$-compressibility as the structural conditions that make the equilibrium response and the Newton corrector evaluable from a retained streaming statistic. The theory is instantiated in latent linear Gaussian covariance estimation, where the first-order scheme operates on a compressed $d \times d$ statistic with explicit finite-sample risk envelopes and a certified restart rule.
Read the full abstract

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

A Closer Look on the Influence of Constraints Upon the Optimization of the Nonadditive Entropic Functional $S_{q}$

The thermal-equilibrium canonical distribution is currently obtained by maximizing the Boltzmann-Gibbs-von Neumann-Shannon entropy $S_{BG}(p)=k\sum^{W}_{i=1}p_{i}\ln 1/p_{i}$ constrained to $\sum^{W}_{i=1}p_{i}=1$ and $\sum^{W}_{i=1}p_{i}\,e_{i}=U$, $e_{1}\leq\ldots\leq e_{W}$ being the energies of the $W$ possible states and $U\in[e_{1},e_{W}]$ their mean value. We revisit a generalized version of this optimization problem grounded in the nonadditive entropy $S_{q}(p)=k\,(\sum^{W}_{i=1}p_{i}^{q}-1)/(1-q)$ (frequently, though not necessarily, $q\in(0,1)$; $S_1=S_{BG}$), and the constraint $\sum^{W}_{i=1} p_{i}^{q^{\prime}}e_{i} / \sum^{W}_{i=1}p_{i}^{q^{\prime}}=U$, $q^{\prime}>0$. Sufficient conditions for existence, strict positivity, and uniqueness of solutions are derived, along with a theorem that enables their closed-form calculation. We apply these results to deepen the understanding of the two standard cases in the literature ($q^{\prime}=1$ and $q^{\prime}=q$), as well as of a new one ($q^{\prime}=2-q$). We prove that these standard cases are the only ones yielding optimizing probability distributions of $q$-exponential form. Furthermore, we define an effective temperature $T_{q,q^{\prime}}$ through a Clausius-like relation $1/T_{q,q^{\prime}}=\partial S_{q} / \partial U$ and derive a Helmholtz-like energy $F_{q,q^{\prime}}=U-T_{q,q^{\prime}}S_{q}$, with the former grounding the validity of the $0^{th}$ Principle of Thermodynamics within this generalized statistical mechanics. Finally, we show that the case with a linear constraint (i.e., $q^{\prime}=1$) with $q\in(0,1)$ (i) preserves the Third Law of Thermodynamics; (ii) can be used to model classical many-body Hamiltonian systems with arbitrarily-ranged interactions; and (iii) resembles features of low-dimensional nonlinear dynamical systems at the edge of chaos.
Read the full abstract

Optimization and Control

Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent

We propose Broximal Gradient Descent (BroxGD), a projection-free sister method to projected gradient descent for constrained optimization. Its forward–backward construction replaces the proximal backward operation by the broximal operation of Gruntkowska et al. (2025). Instead of projecting, each step minimizes a linear function over the intersection of the constraint set $\mathcal{X}$ and a ball $\mathbb{B}(x_k,t_k)$ centered at the current iterate $x_k$, of suitable radius $t_k>0$: \[ x_{k+1}\in\arg\min_{z\in\mathcal{X}\cap\mathbb{B}(x_k,t_k)}\langle\nabla f(x_k),z\rangle. \] We develop a comprehensive convergence theory spanning a wide range of optimization regimes and radius rules. We expect BroxGD to find many applications and inspire numerous extensions, much like projected gradient descent. Our contribution is theoretical; potential applications and toy experiments illustrate the method and suggest directions for future work.
Read the full abstract

Combinatorics

Ramsey-type $\chi$-bounds for $\chi$-bounded graph classes

We prove that for every path $P$, the class of graphs with no induced $P$ and no induced four-cycle $C_4$ is linearly $\chi$-bounded. More generally, we ask for which pairs $\{T,H\}$ where $T$ is a forest and $H$ is a complete multipartite graph, every graph $G$ with no induced $T$ and no induced $H$ has chromatic number at most $C \cdot R(\alpha(H),\omega(G)+1)$ for some constant $C$ depending only on $T$ and $H$, where $R(\cdot,\cdot)$ denotes the usual Ramsey numbers. We show that this holds in the following two instances, which strengthen the case $T=P$ and $H=C_4$ mentioned above: (1) every component of $T$ is a broom and $H$ is complete multipartite; or (2) $T$ is a forest and $H$ is complete bipartite. These two unify and substantially extend a number of previous results on linear and polynomial $\chi$-boundedness for various graph classes. For case (2), we also provide a new proof (with better bounds) of a recent result of Fox, Nenadov, and Pham on the existence of an induced copy of a fixed tree in a graph satisfying certain sparsity conditions.
Read the full abstract

Number Theory

Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes

We present a special-purpose algorithm for factoring semiprimes $N = pq$ in which one prime factor satisfies $p \approx c\,(a/b)^n$ for positive integers $a, b, c, n$ with $a > b$ and $\gcd(a,b) = 1$. Given the correct parameters $(a, b)$, the algorithm isolates a factor in ${O}(\log^3 N)$ time when $a/b$ is bounded away from $1$, and the cofactor $q$ is unconstrained beyond a mild size bound. We describe a search strategy over $(a, b)$ using primitivity filters, give a complexity analysis showing that the method poses no threat to balanced RSA semiprimes, and provide a gmpy2-based Python implementation.
Read the full abstract