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)

Friday 14 August

Numerical Analysis · Cross-listed from stat.ME

Semi-supervised Concordance Learning for Optimal Individual Treatment Regimes

Finding the optimal individualized treatment rule that maps individual characteristics or contextual information to treatment assignments has been extensively investigated in existing literature, with widespread practical applications. This paper considers the estimation of optimal treatment regimes within a semi-supervised data framework (exemplified by electronic medical record data). In such settings, only a tiny proportion of observations have observed outcome labels, owing to high labeling costs, time limitations, data privacy concerns, and other constraints, while covariates and treatment assignments are available for all study subjects. We develop a semi-parametric inference method for optimal treatment regimes, which leverages outcome- unlabeled samples with complete covariate and treatment information to enhance estimation efficiency. The proposed estimation framework consists of two key steps: first, flexible nonparametric imputation via single-index kernel smoothing; second, subsequent estimation of the optimal treatment regime based on concordance-assisted learning. We establish the consistency and asymptotic normality of our proposed estimators. Numerical simulation studies demonstrate that our method achieves higher efficiency and stronger robustness relative to fully supervised estimators under finite-sample settings. We further validate the practical value of our proposed framework using the MIMIC-III and ACTG175 datasets.
Read the full abstract

Dynamical Systems

An intrinsic characterization of the Bogdanov-Takens normal-form coefficients and a mixed-volume obstruction to non-isolated degeneracies

Let $X$ be a planar vector field with an equilibrium $p$ at which the Jacobian $J=DX(p)$ is nilpotent of rank one, and let $q_0$ span $\ker J$. We prove that the two coefficients $a$ and $b$ of the Bogdanov–Takens (BT) normal form are the directional derivatives, along $q_0$, of the two invariants of the Jacobian: $a=-\frac{1}{2}\langle\nabla\det DX(p),q_0\rangle$, $b=\langle\nabla\operatorname{tr}DX(p),q_0\rangle$. The identity is invariant under changes of phase-space coordinates and equivariant under the rescaling of $q_0$, and the resulting formula requires neither generalized eigenvectors nor the second-order multilinear form. It yields a coordinate-free reading of the BT nondegeneracy conditions in terms of the kernel line field of the projection of the equilibrium manifold onto parameter space, the transformation rule $(a,b)\mapsto(h^2a,hb)$ under orbital equivalence, and the fact that $a=0$ whenever the vector field factors through a function vanishing at $p$. We then prove an obstruction of a combinatorial nature. For a Kolmogorov system $\dot{x}=xA/g_1$, $\dot{y}=yB/g_2$ and an equilibrium $p$ in the torus $(\mathbb{C}^*)^2$ at which the Jacobian is nilpotent and nonzero, the order $m=\operatorname{ord}f$ in the Takens normal form is bounded by the mixed volume of the Newton polytopes of $A$ and $B$. In particular, if $\operatorname{MV}(\operatorname{Newt}A,\operatorname{Newt}B)\leq2$ then $a\neq0$ unless the equilibrium fails to be isolated, and the nilpotent singularities of saddle, focus and elliptic type are unreachable: only cusp-type singularities occur at isolated equilibria, while their exact codimension is not controlled by the mixed-volume bound. The class of systems with cross-product cubic terms, for which the mixed volume equals $2$, is treated in detail, and two classical Bazykin models are shown to be instances.
Read the full abstract

Classical Analysis and ODEs

Transversal Hölder Criteria and Dini–Zygmund Endpoint Regularity for Hyperbolic Harmonic Mappings

Let $n\ge3$, and let $u$ be a bounded hyperbolic harmonic mapping on the real hyperbolic upper half-space $\mathbb H^n$. First, for $0<\alpha<1$, we establish quantitative transversal and modulus criteria for the global $\alpha$-Hölder continuity of $u$. Then, we construct lacunary examples to show that these criteria are invalid when $\alpha=1$. Finally, under additional integral conditions, we obtain the corresponding global Lipschitz continuity and give Dini–Zygmund conditions on the boundary trace that ensure the Lipschitz continuity.
Read the full abstract

Information Theory

A Structural Characterization of Entropy Functionals

Entropy functionals and their associated divergences underlie many statistical methods, including maximum entropy inference, minimum divergence estimation, and goodness-of-fit testing, yet choosing among Shannon, Rényi, Tsallis, and more general entropies is often a matter of convention rather than structural principle. We introduce a measure theoretic framework in which admissibility requires the entropy of an input measure to be bounded above by that of its reference measure whenever the former is absolutely continuous with respect to the latter. Under generalized mean-value composition, we characterize all such entropy functionals and obtain a four-level hierarchy determined successively by the mean generator, entropy scale, and additivity assumptions. A continuous strictly monotone generator $g$ is admissible exactly when $t\mapsto g(1/t)$ is strictly convex for increasing $g$, or strictly concave for decreasing $g$. This resolves a question posed by Rényi (Proc. 4th Berkeley Sympos. Math. Statist. Prob., 1961) concerning which generalized means may replace the arithmetic mean in his entropy axiomatization. The same criterion is equivalent to strict convexity of an associated Csiszár $f$-divergence generator and therefore yields data processing under Markov kernels with an exact equality condition. Within this hierarchy, product additivity singles out the Rényi family, while internal additivity, or product additivity together with arithmetic mean-value composition, singles out Shannon entropy. The characterization is constructive and yields new admissible entropy and divergence families, including integral-transform examples.
Read the full abstract

Algebraic Geometry

Rank-two weak Fano bundles on a four-dimensional quadric hypersurface $Q^4$

We classify rank $2$ weak Fano bundles on a four-dimensional smooth quadric hypersurface $Q^4$. Up to twisting with a line bundle, such a bundle is either a split bundle, a spinor bundle, or one of the stable bundles with Chern classes $c_1=-1$ and $c_2=(1,1)$ constructed in [APW94].
Read the full abstract

Optimization and Control

First-Order Optimization as Minimum-Time Control

We formulate first-order optimization as a minimum-time control problem. The iterate is the state, the update, a combination of the gradients observed so far, is the control, and the points with gradient norm at most a prescribed tolerance form the target set. For a fixed objective and start, the minimum number of oracle queries needed to reach the target is a value function: it measures the complexity of the instance, not the worst case over a class. On a strongly convex quadratic, the conjugate gradient iterates emerge from the discrete Pontryagin conditions, and the value is a controllability index. Beyond the quadratic, a Hessian-generated reachable span replaces the controllability matrix, and feasibility becomes a reachability question: whether a critical point can be reached at all, and in how many steps, is read from the span. Curvature is a resource: a checkable condition certifies that an instance needs fewer steps than the controllability index of its quadratic model at the minimizer, and the gap can grow without bound with the dimension. The value is thus a benchmark for the intrinsic difficulty of each instance, against which any first-order method can be measured.
Read the full abstract

Information Theory

New lower bounds for constant-weight codes via seeded bit-swap tabu search

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $\tau_{32}$, $\tau_{33}$, $\tau_{34}$, and $\tau_{37}$.
Read the full abstract

Functional Analysis

Fractional Powers of Operators: Characterization via $\delta$-Regularized Logarithmic Representation

For the fractional powers of operators, the classical formulation by V. Balakrishnan inherently requires positivity or specific sectorial conditions of the generator (i.e., the generation of analytic semigroups). To overcome these limitations, this paper presents a novel approach to constructing fractional powers of operators $D^k$ through the $\delta$-regularized logarithmic representation of infinitesimal generators $D$, based on the framework of $C^0$-semigroup theory for abstract evolution equations in Banach spaces. The proposed method bypasses the conventional geometric constraints by employing an algebraic $\delta$-regularization for bounded operators. Specifically, by applying a complex-analytic logarithmic representation to a family of bounded operators derived from the resolvent of the semigroup, we mathematically prove that, under the minimal algebraic assumption of invertibility, the fractional powers for generators of more general $C^0$-semigroups are uniquely and rigorously well-defined, independent of the choice of the regularization parameter $\delta$. The theoretical framework established in this study offers extensive potential for applications, including regularity estimates for non-analytic semigroups and non-autonomous systems where the infinitesimal generators depend explicitly on the time variable.
Read the full abstract

Logic

Does the Hardin-Taylor Predictor Actually Predict the Future? Yes; but Only in Retrospect

The Hardin-Taylor theorem, a consequence of the axiom of choice, gives a strategy to predict future values of an arbitrary function of time $f:\mathbb{R}\to S$ given its past values. The times in $\mathbb{R}$ at which the strategy fails are shown to form a countable nowhere dense set for any function $f$. The theorem is often presented as a striking result about predicting the future. In this note we discuss the operational content of the theorem and clarify this frequent interpretation. The Hardin–Taylor prediction strategy is online: at time $t$ it depends only on the observed past $f \upharpoonright (-\infty,t)$. Its performance guarantee, however, is offline: the exceptional set consisting of times at which the predictor fails is defined only after the entire function has been realized. We spell out the precise definition of the predictor, discuss a simple two-function example as a sanity check, and emphasize the retrospective nature of verifying the predictor's success. We also examine the proper probabilistic setting in which the success likelihood of the predictor as a forecasting procedure should be evaluated. Our conclusion is that the theorem is best understood as a result about the smallness of the set of times at which the predictor must be course-corrected, rather than as a prospectively verifiable procedure for forecasting the future.
Read the full abstract

Rings and Algebras

Mittag-Leffler Conditions, Gorenstein Modules and Homological Invariants

In this paper, we investigate certain properties on the Mittag-Leffler conditions via set-theoretic methods. We establish that a strongly $\aleph_1$-presented module $M$ satisfying Ext$_R^{\ge 1}(M,D^{(\aleph_1)})=0$ belongs to the left orthogonal class of $\overline{D}$, where $\overline{D}$ is the definable of $D$. This yields the consequence that every $\aleph_1$-generated strongly Gorenstein projective module is Gorenstein flat. Furthermore, we investigate when a flat Gorenstein projective module is projective. Finally, for any two-sided $\aleph_1$-coherent ring $R$, we prove the identity $\operatorname{silp}R+\operatorname{silp}R^{\mathrm{op}}=\operatorname{spli}R+\operatorname{spli}R^{\mathrm{op}}$.
Read the full abstract

Algebraic Geometry

Twisted forms of classical hypersurfaces

We count the twisted forms, over the field of real numbers and over finite fields, of the three classical families of smooth hypersurfaces with large automorphism group: the Fermat, Delsarte and Klein hypersurfaces. Our main tool is a counting formula for the Galois cohomology set of a smooth hypersurface whose automorphism group is the semidirect product of a diagonal abelian group and a group of permutations of the monomials of its defining equation. In order to apply this formula over finite fields, we extend the differential method of Oguiso and Yu to positive characteristic, and we compute the automorphism groups of the Fermat, Delsarte and Klein hypersurfaces over algebraically closed fields of positive characteristic under explicit arithmetic conditions on p. Over the reals, our count recovers a recent theorem of Sasaki on the real forms of Fermat hypersurfaces.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

de Broglie-Bohm Dynamics with Schrödinger Source Fields: A Framework for Subquantum Theory

We extend de Broglie–Bohm (dBB) pilot-wave theory by introducing a complex source field into the Schrödinger equation and examining its effects on quantum equilibrium and nonequilibrium dynamics. In dBB theory, the physical particle distribution P, rather than the Born density $|{\psi}|^2$, carries the ensemble probability, so a source term may modify the pilot wave without violating conservation of total particle probability. We derive the source-modified Hamilton–Jacobi and continuity equations, the transport equation for the nonequilibrium ratio $f=P/|{\psi}|^2$, and an exact entropy-production formula. Three applications follow. First, suitably designed sources can drive exponential relaxation toward quantum equilibrium. Second, the entropy-production rate admits a Prigogine-type bilinear form, providing a basis for a subquantum thermodynamics with entropy-producing and entropy-extracting regimes. Third, a tuned source can exactly cancel the Bohmian quantum potential, yielding classical particle trajectories while the guiding wave retains nontrivial structure and the nonequilibrium ratio remains conserved. The resulting framework provides a unified setting for studying source-driven quantum nonequilibrium, entropy exchange, and classicalization, and motivates further investigation of the physical and ontological status of the source field.
Read the full abstract

General Mathematics

On a Generalization of Zumkeller Numbers: Infinitude of odd $k$-IGMO numbers for all non-negative integers $k$

In this paper, we introduce and investigate a novel generalization of Zumkeller numbers termed $k$-IGMO numbers, inspired by a problem proposed in the International Gamma Mathematical Olympiad (IGMO) 2025. A positive integer n is defined as a $k$-IGMO number if its set of positive divisors can be partitioned into two disjoint subsets whose elements have sums differing by $k$. Under this definition, classical Zumkeller numbers correspond to the case where $k = 0$. The main result of the paper is the existence of infinitely many odd $k$-IGMO numbers for all non-negative integers $k$.
Read the full abstract

Rings and Algebras

Sum of two strictly n-zero matrices

In this work we investigate when an $n\times n$ Jordan matrix can be written as the sum of two strictly $n$-zero matrices. In particular, we show that if $\mathbb{F}$ is an algebraically closed field of characteristic zero and $A$ is an $n\times n$ matrix over $\mathbb{F}$ with $\tr(A)=0$, then $A$ is the sum of two strictly $n$-zero matrices.
Read the full abstract

Dynamical Systems

Mixing for Free Semigroup Actions of Blaschke Products on the Circle

We study mixing at a double exponential rate on analytic observables and ask how much of a map is remembered by its rate of mixing. For finite Blaschke products of the circle with a fixed point in the unit disk, and for the free semigroup actions they generate, we give a complete classification: the rate of mixing (no mixing, exponential, or double exponential) is determined by the multiplier of the generators at that fixed point, the invariant measure being the harmonic measure with a pole there. In the double exponential regime, the exponent equals $\log p$, where $p$ is the minimal local degree of the generators at the fixed point, and we show that this value is sharp. Consequently, the rate is not rigid: it is not stable under $C^1$-perturbations and does not imply $C^1$-conjugacy to affine models. Rigidity holds when the exponent is maximal for the degree: a map of degree $q$ whose exponent attains $\log q$ is Möbius conjugate to an affine model.
Read the full abstract

Numerical Analysis

PDE Realization and Structure-Aware Solvers for a Compact Two-Stage Fourth-Order IMEX Method

This paper develops a PDE realization and solver framework for a compact two-stage fourth-order two-derivative implicit–explicit time discretization for stiff split problems. The key difficulty is a consistency–cost coupling: full-field temporal differentiation is required to preserve the mixed explicit–implicit interactions of the time integrator, but the same interactions widen the implicit stage operators and can make each solve substantially more expensive. We show that a second-order ADER/Cauchy–Kowalevski local evolution is sufficient for the fourth-order outer composition, establish smooth reconstruction consistency and a fully discrete error balance, and derive the leading Lie-bracket defect produced by self differentiation of the split fields. An inexact-stage analysis gives asymmetric midpoint and endpoint residual tolerances that preserve fourth-order accuracy. For the widened stages, the complete mixed action is retained matrix-free while only dominant stiff physics is approximated in the inverse. This yields quadratic and shifted preconditioners, Fourier and multilevel realizations, a semilinear reaction–diffusion reduction, and source-local elimination for relaxation systems. Exact quadratic cancellation, a diffusion-dominated Fourier estimate, and an $\varepsilon/\Delta x$ bound for Jin–Xin relaxation explain the main solver mechanisms. Numerical ablations verify the consistency and tolerance results, while a two-dimensional Brusselator study on two grids shows favorable error-versus-wall-time behavior over a useful accuracy range. A classical stiff-front benchmark also identifies the separate spatial shock–source limitation. The results support a regime-dependent efficiency claim rather than a universal speedup.
Read the full abstract

Quantum Algebra

$C_2$-Cofiniteness and Rationality of the Icosahedral Orbifold $V_{L_2}^{A_5}$

Let $L_2=\mathbb{Z}\alpha$ be the rank-one root lattice with $(\alpha,\alpha)=2$, and let $A_5$ act on the lattice vertex operator algebra $V_{L_2}$ through an icosahedral subgroup of $\operatorname{Aut}(V_{L_2})\cong PSL_2(\mathbb{C})$. We prove that the fixed-point vertex operator algebra $V_{L_2}^{A_5}$ is strongly rational.
Read the full abstract

Statistics Theory

Generalization Error Estimation for Primal–Dual Algorithms in Non-Smooth Regression

This paper studies trajectory-wise estimation of generalization error for primal–dual algorithms in non-smooth regression. Motivating examples include \(\ell_1\)-penalized least absolute deviations regression and square-root Lasso regression, where the data-fitting loss is non-differentiable and existing risk estimators for gradient-type optimization paths do not apply directly. We develop a general recursive framework that includes the Chambolle–Pock algorithm and related primal–dual splitting methods. We estimate risk by correcting each in-sample fitted value with a weighted combination of past dual iterates. The ideal weights are Stein derivative contractions and depend on the design covariance. We construct replacement weights from observable derivative contractions of the fitted-signal trajectory, yielding a covariance-free, data-driven correction. For high-dimensional Gaussian designs and fixed finite iteration horizon, we prove finite-sample guarantees for both estimators. For square-root ridge, we further establish a matched-Gaussian universality result beyond Gaussian designs. Numerical experiments show that the proposed estimators accurately track the out-of-sample risk along finite optimization paths.
Read the full abstract

Representation Theory

Exactness and Drinfeld-Sokolov Realization of the McRae-Yang Tensor Functors

Let $p,q\ge 2$ be coprime, set $k=-2+p/q$, $k'=-2+q/p$, and let $c_{p,q}=1-6(p-q)^2/(pq)$. We prove that the McRae–Yang functors $F_{p,q}\colon KL^k(\mathfrak{sl}_2)\to\mathcal O_{c_{p,q}}$ and $F_{q,p}\colon KL^{k'}(\mathfrak{sl}_2)\to\mathcal O_{c_{p,q}}$ are exact and faithful, and, as $\mathbb C$-linear functors, are naturally isomorphic to the corresponding principal quantum Drinfeld–Sokolov reductions. Their restrictions to projective objects are fully faithful.
Read the full abstract

Information Theory

The Capacity Region of the Multiple Access Channel with Non-Signaling Assistance

The capacity region of the $K$-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all $K$ transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to $K$ senders of an outer bound that was previously established by Fawzi and Fermé for $K=2$ senders. Additionally, we provide examples of $K$-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to $K$. Combined with an upper bound from prior work, this establishes $K$ as the extremal value of the multiplicative gain from NS-assistance across all $K$-sender MAC settings.
Read the full abstract

Dynamical Systems

A classification of bicritical dynamic portraits

The dynamic of a rational map $f:\widehat{\mathbb C}\to \widehat{\mathbb C}$ is determined by the forward orbits of its critical points. Such a map is called postcritically finite if every critical point has finite forward orbit, or equivalently, if every critical point eventually maps into a periodic cycle. These orbits can be encoded in a finite directed graph called a dynamic portrait. In this work, we classify which abstract bicritical dynamic portraits of degree $d\geq2$ with at least 4 postcritical points are realizable exclusively by rational Thurston maps.
Read the full abstract

Analysis of PDEs

Review of well-posedness methods for the 1D nonlinear Schrödinger equation with an application to combined nonlinearities

We consider the nonlinear Schrödinger equation in one dimension with nonlinearities of type $|u|^\alpha u$ for any power $\alpha>0$ and review two different methods for obtaining solutions, namely, local well-posedness, with initial data either in $L^2$ or $H^1$, or in the weighted subspace of $H^1$. One approach is based on the Strichartz estimates, and thus, $H^1$ well-posedness typically holds for nonlinearities with power $\alpha \geq 1$. The other one is a direct application of weighted estimates commuting with derivatives and a certain infimum condition on the initial data, and thus, can treat nonlinearities for the whole range $0 < \alpha < \infty$; furthermore, it can handle a sum of different nonlinearities. We then conclude with an application of the second approach to the NLS with finitely many combined nonlinearities, important for physical applications (e.g., in laser optics), as it is more challenging, if at all possible, to obtain local well-posedness with the first method due to the lack of scaling invariance.
Read the full abstract

All authors Alex D. Rodriguez, Gia Azcoitia, Hannah Wubben, Svetlana Roudenko

Numerical Analysis

Vanishing Clutter: Fast and Accurate Shape Imaging via Active Cloaking

Imaging a target sample in near-field scanning optical microscopy (NSOM) is fundamentally limited by measurement artifacts and data contamination from multiple probe-sample scattering. The probe, essential for subwavelength resolution, inherently perturbs the local field, degrading the signal-to-noise ratio and rendering the inverse problem for quantitative shape reconstruction highly ill-posed. We first establish the well-posedness of the corresponding forward model, providing a rigorous foundation for subsequent imaging. We then repurpose active cloaking–conventionally the antagonist of imaging–as an enabling mechanism to eliminate probe-induced interference. Rather than directly reconstructing the sample from corrupted data, we actively cloak the probe by formulating an optimal control problem and prove the existence and stability of its minimizers. Leveraging the theory of localized anomalous resonance in layered plasmonic structures, we derive an exact closed-form minimizer, thereby circumventing the computationally prohibitive iterative solution of the optimal control problem. The resulting cloaking-driven interference removal yields a virtually probe-free measurement environment, enabling fast, artifact-free shape reconstruction. Extensive numerical experiments demonstrate accurate shape reconstruction and dramatic acceleration–often by orders of magnitude–over conventional iterative methods applied directly to probe–contaminated data without cloaking–based preprocessing, validating the robustness and transformative potential of the proposed approach for high-fidelity subwavelength imaging.
Read the full abstract

Thursday 13 August

Algebraic Geometry

Projective blowups: a formal and multicentered proof

We give a machine-checked proof, in Lean 4, of the universal property of multi- centered blowups: given a finite family Z of closed subschemes of a scheme X, presented on each chart by ideals, there is a scheme BlZ X over X, terminal among X-schemes on which every member of the family becomes an effective Cartier divisor. To the best of our knowledge this is the first formalisation of blowups, single- or multicentered, in any theorem prover. The proof is organised around the universal property of the multicentered dilatation of a ring. The comparison isomorphisms on overlaps, the cocycle identity, and the independence of the chosen presentation are obtained from the uniqueness part of this universal property. We give the exact theorem statement as formalized, the proof architecture, and the main new mathematical ingredients, together with the corresponding Lean code.
Read the full abstract

Statistics Theory · Cross-listed from cs.GT

A Statistical Analysis of Three Player Auction Bridge

Three-player Auction Bridge is a finite imperfect-information game in which dynamic partnerships create a distinctive interaction between scoring, strategic incentives, and payoff distribution. This paper develops a unified statistical and game-theoretic framework to evaluate a traditional scoring rule against a modified mechanism designed to improve strategic incentives. We first identify a structural defect in the original scheme: a bid-invariant slam bonus can make lower contracts strictly more attractive than higher ones. A bid-dependent correction removes this incentive distortion. We then compare the two schemes using higher-moment analysis, fairness measures, Nash equilibrium analysis, and General-Sum Counterfactual Regret Minimization (GS-CFR). The results show significant differences in the shape of the payoff distributions and reveal that, although both schemes remain highly balanced across physical seats, the modified scheme substantially increases inequality across strategic roles. The game is shown to be neither zero-sum nor constant-sum, motivating a general-sum rather than minimax analysis. Full-game GS-CFR further indicates a substantial increase in the bidder's payoff under the modified scheme, accompanied by a reduction in defender payoff and a shift from separating to partially pooling bidding behavior. These findings demonstrate that scoring-rule design can fundamentally reshape incentives, payoff distribution, and information transmission in imperfect-information games. The proposed framework provides a systematic approach to evaluating such mechanisms from both statistical and strategic perspectives.
Read the full abstract

Optimization and Control · Cross-listed from cs.DS

Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs

We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location $y$ clears all pending requests in $[0,y]$ at cost $y$. In the classical adversarial setting, we propose an $e$-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus $e$ is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter $\lambda\in(0,1]$, our deterministic learning-augmented algorithm is $(1+3/\lambda)$-robust and $(1+3\lambda)$-consistent. We also propose a randomized learning-augmented algorithm that is $(e+e/\lambda)$-robust and $(e-1+\lambda)$-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.
Read the full abstract

Information Theory · Cross-listed from cs.CR

CRT-Decomposed $\Sigma$-Protocols for CSIDH

We construct a zero-knowledge proof of knowledge for the CSIDH group action that exploits the Chinese Remainder Theorem (CRT) structure of the ideal class group, available whenever the group structure is known exactly, as for CSIDH-512. We prove perfect completeness, perfect special honest-verifier zero-knowledge, and 2-special soundness, in which the secret is recovered from two accepting transcripts by one subtraction and one modular inversion per CRT component; no rewinding loop, lattice reduction, or heuristic sampling appears in the extractor. Because each round admits exactly two responses, Unruh's transform yields a non-interactive proof with straight-line extraction in the quantum random oracle model (QROM), removing the multiplicative forking-lemma loss. We instantiate the scheme on the CSIDH-512 class group, verify the algebraic layer by machine over the exact 258-bit modulus ($10^4$ random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven $2^{-t}$ bound within 95% confidence at every tested $t$, serialized signature sizes within 1.6% of the formulas, instrumented action counts, and a scaled meet-in-the-middle attack whose measured cost follows the predicted $\sqrt{q}$ law. We further prove two delimiting results: CRT decomposition cannot enlarge the per-round challenge space, and publishing the CRT hop curves lowers classical key-recovery cost from about $2^{128.6}$ to about $2^{67.3}$ group action evaluations. The construction is therefore correct and structurally complete today, but quantitatively secure only on future parameters whose class number has large prime factors. We compare against CSI-FiSh, CSI-Otter, and Tanuki; a tightly secure blind signature from this proof of knowledge is left to future work.
Read the full abstract

Mathematical Physics · Cross-listed from physics.flu-dyn

Exact linearisation of the nonlinear shallow-water equations over a moving bottom: classification, wave generation and run-up

The Carrier–Greenspan hodograph transformation linearises the nonlinear shallow-water equations on a beach of constant slope. We extend the transformation to a moving bottom and identify the family of bottom motions that preserves the Carrier–Greenspan invariants. The bottom gradient must be uniform in space, that is, $h(x,t)=\rho(t)x+\mathcal{B}(t)$, and constant $\rho$ returns the classical slope. For this family a horizontally accelerating frame removes the forcing. The bottom motion then disappears from the hodograph equation, and two quadratures recover the physical variables. If the gradient varies in time, the bed displacement grows without bound offshore and the far field cannot remain at rest. The domain must therefore be finite, although the pivot may be placed anywhere. A bottom-tilting wave maker realises this family. Closed forms follow for the hinge response, for the crest-to-trough steepness of the generated wave, and for the leading nonlinear correction. The correction depends on the point to which the steepness is referred, and so differs between a leading-elevation and a leading-depression wave. Because the hinge is at the beach toe, these closed forms provide the incident wave required by the classical plane-beach solution. The run-up can therefore be predicted from the plate motion alone. The steepness is predicted without a fitted constant and agrees with the reference computations. Sixty-one runs over a level bed, reported here for the first time, carry the test to deeper water and longer plate motions. The measured run-up follows the predicted run-up, with an offset that the inviscid theory does not account for.
Read the full abstract

Combinatorics

Sparse chromatic graphs and the complete-graph triangle bound

We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order $O(r)$ and chromatic number at least $(1-\eta)r$. Second, we prove an order-uniform stability theorem: for every $\beta>0$ there is $\gamma>0$, independent of the constant in the linear order bound, such that every sufficiently large $s$-critical graph $J$ of order $O(s)$ with $\omega(J)\le (1-\beta)s$ has at least $\binom s3+\gamma s^3$ triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least $(1-\delta)r$. This uses a new dense common-palette list analogue of Harris's edge–triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.
Read the full abstract