Information Theory
Multiple Access in Pinching-Antenna Systems: A Survey, Impairment Analysis, and Evaluation
Wei Jiang and Hans Dieter Schotten
Pinching-
antenna systems attach dielectric pinches to a waveguide, creating line-of-sight radiation points within a few meters of any user. The pinches on one waveguide, however, radiate the same signal, unlike a conventional array, where each element transmits a dedicated signal. Separating the signals of multiple users therefore becomes challenging and requires a new perspective on multiple access. Most existing studies rest on an idealized model, and no survey examines the access schemes under realistic impairments. This article surveys multiple access in pinching-
antenna systems and organizes fifty-six works into a unified taxonomy by spatial degrees of freedom. The users of one waveguide can be separated only in time, frequency, power, or guided mode, while multiple waveguides add the space domain. The article then identifies the impairments critical to this separation, which perturb the effective channel, leak interference across orthogonal resources, or couple the pinches on the uplink, and summarizes them in an impairment-versus-method map. A unified evaluation of time-, frequency-, power-, and space-domain access under identical channel and impairment models reveals that the degradation is method specific. The analytical and numerical results give insight into multiple access in these systems and provide a basis for its impairment-aware design, a necessary step toward their adoption in practical networks.
Read the full abstract ▾
General Mathematics
The upper semi-Fredholm radius, extensions of restrictions, and subprojectivity
Abdelhalim Azzouz
For a bounded operator $T$ between
Banach spaces, let $d_+(T)$ be its distance to the operators that are not upper semi-Fredholm, and let $\inn(T)$ be Schechter's quantity $\inf\|T|_M\|$ over infinite-dimensional subspaces $M$. One always has $\inn(T)\le d_+(T)$, and González and Martinón showed that the two quantities are not equivalent in general. We prove that $d_+(T)$ is the infimum of the norms of operators on the whole space that extend a restriction of $T$ to some infinite-dimensional subspace. The gap between $\inn$ and $d_+$ thus becomes an extension problem, and projection constants enter naturally. If the domain is uniformly subprojective with constant $\lambda$, then $d_+\le\lambda\,\inn$. In the other direction we prove a quantitative obstruction: a complemented Hilbertian subspace all of whose infinite-dimensional subspaces have projection constant at least $\Lambda$ produces operators with $d_+/\inn\ge\Lambda/2$. Consequently, on the subprojective but not uniformly subprojective space $(\bigoplus_nL_{p_n})_{\ell_2}$ with $p_n\to\infty$, there is no uniform comparison between $\inn$ and $d_+$. We
conjecture that uniform comparison is equivalent to uniform subprojectivity. Finally, we compute $\inn$ for inverses and for shears in terms of the quantity $\tau(T)=\sup_M j(T|_M)$, and we use the arbitrary distortability of
Hilbert space to show that a rectangular diagonal operator $\operatorname{diag}(A,B)$ built from two isomorphisms with $\inn(A)=\inn(B)=1$ can have arbitrarily small $\inn$. In contrast, every operator $T$ on a complex
Banach space satisfies $\inn(T)\le\tau(T)$, so every
automorphism satisfies $\inn(T)\,\inn(T^{-1})\le1$ and the same mechanism cannot work for endomorphisms.
Read the full abstract ▾
Quantum Algebra · Cross-listed from quant-ph
Predicting Noise in a Trapped-ion Quantum Simulation of a Lattice Gauge Theory
Hassan Ugail
A recent trapped-ion experiment realised a
lattice gauge theory in which the internal states of the ions carry the gauge field and their vibrations carry bosonic matter. In that experiment, a charge moving around a loop was frozen in place by Aharonov–Bohm interference. The noise of such a device is usually simulated after the measurements have been made. Here we show that it can be predicted before the machine is run. For each quantity that the experiment measures, we derive, from the reported noise rates alone, a formula for how it decays together with a bound it can never exceed. The results reveal a simple pattern. The local conservation law of the theory is a parity of the vibrational mode, so heating violates it at a rate that grows as the mode warms, and the violation accelerates rather than accumulating steadily. At zero electric field, each of the three noise processes of the device leaves its own fingerprint. Heating affects only the conservation law, motional dephasing only the interference, and
qubit errors only the stored flux and the frozen state. Once the electric field is switched on, the frozen state begins to leak, and we write an exact formula and a guaranteed bound for that leak.
Read the full abstract ▾
Combinatorics
Spectral Incidence Bounds over Finite Fields
Yao Zhi
Let $\Fq$ be a finite field, let $F,G\in\Fq[T]$ be nonconstant, and let $J\in\Fq[T]$. We study the parameterized two-parameter family \[ C_{a,b}=\{(x,t)\in\Fq^2:t=J(x)+aF(x)+bG(x)+\lambda ab\}, \qquad (a,b)\in\Fq^2, \] where $\lambda\in\Fq^\times$, with incidences counted with parameter multiplicity. If $d=\deg F$, $e=\deg G$, and $\charac(\Fq)>d+e$, we prove the uniform spectral estimate \[ \left|I(\cP,\Omega)-\frac{|\cP||\Omega|}{q}\right| \ll_{d,e}q^{5/8}\sqrt{|\cP||\Omega|} \] for arbitrary $\cP,\Omega\subseteq\Fq^2$. The proof combines two additive
Fourier transforms with a fourth-moment estimate for Kloosterman
matrices. If $1\le d,e\le2$ and $\charac(\Fq)>3$, midpoint–difference coordinates and finite Weyl quantization sharpen the error to the Vinh scale $O(q^{1/2}\sqrt{|\cP||\Omega|})$. We further show that the latter phenomenon is intrinsic to the coefficient curve rather than to the degree of a chosen parametrization. There is a
polynomial Lüroth factorization \[ F=f\circ H,\qquad G=g\circ H,\qquad \Fq(f,g)=\Fq(T), \] unique up to an affine change of $H$. If $\Gamma$ is the plane curve parametrized properly by $(f,g)$ and \[ \kappa_H=\max_{s\in\Fq}|H^{-1}(s)|, \] then finite-fibre pullback multiplies the centered incidence norm by at most $\sqrt{\kappa_H}$. Consequently, if $\deg\Gamma\le2$ and $\charac(\Fq)>3$, then \[ \left|I(\cP,\Omega)-\frac{|\cP||\Omega|}{q}\right| \ll \sqrt{\kappa_H}\,q^{1/2}\sqrt{|\cP||\Omega|}, \] even when $F$ and $G$ have arbitrarily large raw degree. The resulting expansion estimates for $J(x)+yF(x)+zG(x)+\lambda yz$ hold without lower bounds on the individual input sets. In the balanced regime, the $q^3$ missing-value scale for this family is already covered by a
theorem of Arala–Chow; the incidence
theorems here additionally yield expansion consequences in strongly unbalanced regimes.
Read the full abstract ▾
Algebraic Geometry
Mirror symmetry for gCICY threefolds (I): a $[3,-1]$ block and a non-Gorenstein toric phase
Atsushi Kanazawa
We construct and analyze a mirror family for the generalized complete intersection Calabi-Yau threefold $X_+=[\mathbb{P}^1\,|\,3\ {-1};\ \mathbb{P}^4\,|\,2\ 3]$, with $(h^{1,1},h^{2,1})=(2,46)$. An auxiliary-variable presentation turns the negative-degree section into a variation of toric GIT. Crossing one wall flops 16 disjoint $(-1,-1)$-curves and yields a Calabi-Yau threefold $X_-$, a nef complete intersection in a toric $\mathbb{Q}$-Fano eightfold, which carries a genus-one fibration of index 4. Because this ambient space is not Gorenstein, the Batyrev-Borisov construction does not apply. We use the Hori-Vafa equations only to select a 2-parameter Laurent family, and construct a smooth projective crepant compactification $Y$ of the Laurent model with $(h^{1,1},h^{2,1})=(46,2)$; for very general parameters the Mordell-Weil group is $\mathbb{Z}/4\mathbb{Z}$. The periods of $Y$ satisfy a rank-6 Picard-Fuchs system with two maximally unipotent boundary points, whose indicial
algebras are isomorphic to the rational even
cohomology rings of $X_-$ and $X_+$. The resulting genus-zero predictions agree with independent counts of 176 vertical lines and 100 vertical conics on the genus-one fibration $X_-\to\mathbb{P}^2$.
Read the full abstract ▾
Optimization and Control
From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
Kuangyu Ding and Gesualdo Scutari
We study decentralized minimization of sums of smooth strongly convex functions, one per
agent, with communication restricted to neighbors in a graph. Existing decentralized
algorithms typically emulate a centralized method; the network serves only to exchange information, from which
agents approximate the global quantities that the method needs. This paper breaks with this paradigm. We introduce a graph decomposition framework that uses the network to design the method, not merely execute it. It jointly determines how agreement is imposed, which variables are optimized jointly (blocks), and which connected subgraphs host the
agents solving each block. The convergence analysis quantifies the trade-offs among these choices. GATE (Graph-Tearing message passing) instantiates the framework by assigning one dual variable per edge and partitioning the edges into trees.
Agents interleave edge updates with local message passing recursions that summarize optimization within each tree (block). Its surrogate variant, GATE-S, uses tractable local models and compact messages to reduce computation and communication. We establish linear convergence and show that the
topology-aware design acts as a preconditioner: the rate depends jointly on
topology and function geometry through the coupling between subproblems defined on the selected subgraphs, whereas consensus-based optimization methods pay the worst case of each separately, the centralized condition number times the inverse spectral gap. On tree-dominant graphs, convergence is provably faster: the rate scales with the tree diameter, linearly in the number of
agents on rings and barbells against quadratically for non-accelerated consensus-optimization methods. Experiments support the predicted scaling and savings in iterations and communication.
Read the full abstract ▾
Number Theory
Quantitative Gowers uniformity of the primes in intervals of length $X^{5/8+\varepsilon}$
Joni Teräväinen
We prove the first quantitative bounds for the Gowers norms of the von Mangoldt function minus a Siegel corrected model function in short intervals. The result applies to intervals $(X,X+H]$ with $H\geq X^{5/8+\varepsilon}$ and gives quasipolynomial savings for the $U^k(X,X+H]$ norm. The main new ingredient is an efficient non-abelian Type II inverse
theorem with explicit dependence on the nilsequence dimension. We prove this inverse
theorem by applying Leng's efficient equidistribution
theorem in four parameters directly to an unweighted corner correlation in four variables, hence replacing the factorisation and subgroup argument in the non-abelian Type II proof of Matomäki, Shao, Tao and the author. In joint work with Florian Richter, we use this quantitative result as one ingredient in proving the existence of infinitely many sum-product patterns of the form $\{x,x+y,xy\}$ in the shifted
primes $\mathbb{P}-1$.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Quantum estimation, channel orders, and private capacity
Christoph Hirche
Recent examples have shown that zero private capacity need not imply antidegradability and that two channels with zero private capacity can nevertheless transmit private information together. Existing entropic channel orders compare what a receiver and its environment can learn and thereby bound capacities. We connect these orders to the recent constructions through binary estimation, whose minimum mean-square error is governed by measured $\chi^2$ divergence. A new integral representation shows how measured $\chi^2$ on a
qubit extension recovers
quantum $\chi^2$. It lets us pass from complete measured-$\chi^2$ ordering to complete
quantum-$\chi^2$, relative-
entropy, and less-noisy ordering. Zhu and Wang used a signed lift to show that their qutrit channel has zero private capacity. We show that Hermitian-smoothed measured-$\chi^2$ ordering characterizes when such lifts exist, even with a
quantum reference. Environmental dominance in binary estimation at every blocklength yields a finite-code reliability–secrecy bound. These results explain why complete comparison prevents activation with antidegradable helpers whereas regularized comparison alone does not. Building on that qutrit example, we establish this stability for a range of noisy Werner–Holevo channels, determine sharp private-capacity and antidegradability thresholds, and compute exact complementary capacities in a nondegradable range. By contrast, we extend Pauli half-erasure activation to all $1/2\le p<1$ and establish the same range for a new four-level family. Reference-assisted measured-$\chi^2$ witnesses show why these activating constructions lack complete comparison.
Read the full abstract ▾
Combinatorics
Non-isomorphic graphs have distinct vertex-Ramsey classes
Maria Axenovich and Patrick Schmitteckert
For a graph $H$, its $k$-colour vertex Ramsey class is the set of all graphs $G$ such that any colouring of the vertices of $G$ in $k$ colours results in a monochromatic (induced) copy of $H$. We prove that for any $k$, Ramsey classes of any non-isomorphic graphs are distinct.
Probability
Fractal dimension of critical Gaussian free field sign clusters
Alexander Drewitz, Alexis Prévost and Pierre-François Rodriguez
We study metric graph sign clusters of the Gaussian free field on a large class of transient weighted graphs $G$ that are sufficiently low-dimensional, i.e. below the mean-field regime, and prove a macroscopic equivalence property: several natural ways to define macroscopic clusters - involving any of diameter, volume, or capacity functionals - are in fact the same. As a corollary, macroscopic clusters are characterized in low dimensions as those containing large loops in the corresponding loop soup picture, in contrast with the typical behavior in high dimensions. We then apply these results to the small-mesh scaling limit of critical clusters on $\varepsilon\mathbb{Z}^d$, $d=3,4,5$, as $\varepsilon \downarrow 0$. We prove that every subsequential scaling limit consists of sets with positive Brownian capacity whose Hausdorff and Minkowski dimensions are both equal to $1+\tfrac d2$, as conjectured by Werner. We also derive two-point crossing estimates in the limit, and show that each limiting loop soup cluster is the closure of the union of the scaling limits of the macroscopic loops it contains. Remarkably, unlike with planar Bernoulli percolation for instance, the determination of the Hausdorff dimension does not emerge from direct calculations involving a limiting object (such as $\text{SLE}_6$), but rather from the distinctive features of the discrete model itself.
Read the full abstract ▾
Algebraic Geometry
Mirror symmetry for gCICY threefolds (II): $[3,-1]$ blocks, VGIT, and toric phases
Atsushi Kanazawa
The configuration
matrices of generalized complete intersection Calabi-Yau (gCICY) threefolds contain negative entries, so their defining line bundles are not nef and the Batyrev-Borisov construction does not apply directly. We study gCICY threefolds in $\mathbb{P}^1\times B$ with a $[3,-1]$ block, that is, cut out by sections of $O(3)\boxtimes L$ and $O(-1)\boxtimes(L+R)$, where $B$ is a smooth projective fourfold and $2L+R=-K_B$. Auxiliary variables turn the generalized section into a relative variation of GIT, whose opposite phase is the zero locus of a rank-3 bundle on $\mathbb{P}^2\times B$; for general data the two phases are isomorphic or related by $\int_B c_1(L)^4$ disjoint Atiyah flops. Over products of projective spaces there are exactly 18 Calabi-Yau threefold configurations with a $[3,-1]$ block. All of them except the non-Gorenstein case studied in the companion paper have Gorenstein toric nef phases. Thus, for every other configuration in this classification, mirror
symmetry is reduced after variation of GIT to ordinary Batyrev-Borisov duality, which gives the mirror Hodge numbers of the generalized phase itself. We analyze four examples with a $[3,-1]$ block and one outside this class in detail. For each we construct an explicit mirror and compute its fundamental period and low-order Picard-Fuchs system; the indicial
algebras at the maximally unipotent boundary points are isomorphic to the rational even
cohomology rings of the A-model phases.
Read the full abstract ▾
Statistics Theory · Cross-listed from stat.ME
Boundary inference for the Makeham term in mortality models
Silvio C. Patricio
Whether a mortality model needs a Makeham term, the constant representing background mortality, is commonly decided with a likelihood-ratio test. The constant cannot be negative, so testing its absence places it on a boundary, where the usual chi-squared calibration fails. Assuming independent Poisson death counts and standard regularity conditions, we show that when the constant is the only parameter on a boundary the statistic converges to an equal mixture of a point mass at zero and a chi-squared distribution with one degree of freedom: at the 5% level the critical value is 2.71, not 3.84. We state conditions under which the correction holds for Makeham models, verify them for Gompertz–Makeham and gamma-Gompertz–Makeham, and quantify the information about the constant, which fixes the local power, the smallest detectable term, and the loss of detectability as the age window narrows. When a gamma-frailty variance is estimated at a true value of zero, the limit is no longer a chi-squared mixture and the correction rejects too often. Monte Carlo experiments show the conventional cutoff rejecting at half the nominal level, a correctly calibrated test missing a term at its detection threshold in most samples, and excess rejections persisting as exposure grows.
Read the full abstract ▾
Mathematical Physics · Cross-listed from quant-ph
Modified logarithmic Sobolev inequality for 1D non-commuting Hamiltonians
Ángela Capel, David Pérez-García and Matteo Scandi
Given a finite-range, non-commuting
Hamiltonian on a 1D chain of finite
spins, we prove a modified logarithmic Sobolev inequality with constant $\Omega(1/\log n)$ for the heat-bath dynamics, a quasi-local Gibbs sampler, and for the regularised heat-bath dynamics. This implies rapid mixing of both samplers towards the Gibbs state in relative
entropy and trace norm, with mixing times of order $\mathcal{O}(\log n\cdot \log(n/\epsilon))$. The interactions may be spatially inhomogeneous. The proof combines weak quasi-factorisation of relative
entropy, decay-of-correlation estimates, a uniform conditional local gap, and a buffered comparison between conditional
entropy and quadratic energy. The resulting bounded
entropy defect is removed using the global gap. To the best of our knowledge, this is the first proof of MLSI in the non-commuting regime.
Read the full abstract ▾
Algebraic Geometry
Rationality of varieties and $\mathbb{A}^1$-homotopy theory
Utsav Choudhury and Biman Roy
In this article, we present the results relating different rationality properties with $\mathbb{A}^1$-homotopy theoretic invariants.
Quantum Algebra · Cross-listed from quant-ph
Exact Recovery for Non-Abelian Surface Codes
Alison Warman, Nathanan Tantivasadakarn and Sakura Schafer-Nameki
We study exact recovery for non-Abelian topological surface codes based on the
quantum double $D(G)$ of any finite group $G$. We determine an orthogonal error basis, that is comprised of group multiplication and irreducible representation operators. Whenever the errors are supported on closed loops on the
lattice or dual
lattice, there is a redundancy in the basis, due to stabilizers. To remedy this, we introduce a gauge-fixing that results in a complete and orthogonal error basis on the code space. Assuming as input predetermined, neutral correctable error clusters, we construct charge and flux transfer
circuits that move the errors onto ancillas that then get projected out. This is an exact and deterministic recovery protocol, applicable to surface codes for any finite, in particular non-Abelian, group $G$.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Efficient capacity-achieving entanglement generation with application to pure-loss Bosonic channels
Avijit Mandal, Christophe Piveteau, Henry D. Pfister et al. (+1 more)
While the ultimate limits on the rate of
quantum communication over noisy channels are well-established, very few efficient coding schemes achieving these limits are known. This contrasts sharply with transmitting classical data over classical channels, where polar codes and low-density parity-check codes both efficiently achieve the classical capacity of any noisy channel. In this work we construct an efficient
entanglement generation scheme which achieves the coherent information for a broad class of channels. For degradable channels in the class, which includes truncated versions of the pure loss Bosonic channel, the resulting scheme achieves the
quantum capacity. The construction makes use of polar codes for two kinds of classical-input,
quantum-output (CQ) channels: those with commuting outputs and those whose outputs are heralded mixtures of pure states. The former case is amenable to decoding by classical polar decoding
algorithms, the latter by the belief propagation with
quantum messages (BPQM)
algorithm. To our knowledge, this construction is the first explicit and efficiently decodable protocol that achieves the energy-constrained
quantum capacity of the pure-loss Bosonic channel.
Read the full abstract ▾
All authors Avijit Mandal, Christophe Piveteau, Henry D. Pfister, Joseph M. Renes
Analysis of PDEs
On improved Hardy-type inequalities in Log-Weighted Sobolev Spaces
Sourav Ghosh
We prove sharp Hardy-type inequalities in Log-weighted Sobolev spaces. Due to the non-attainability of the sharp constant, we improve these inequalities by adding suitable remainder terms consisting of optimal weights and sharp constants. Consequently, this gives an infinite series improvement in Log-weighted Sobolev spaces. Next, by using these improved Hardy-type inequalities, we also prove an optimal Leray-Trudinger-type improvement. Furthermore, we derive interpolation between Hardy-type inequalities and Leray-Trudinger-type inequalities.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.LG
Planning to Learn
Ian Osband
Policy-gradient methods are central to modern reinforcement learning, including LLM post-training. When they struggle, the usual suspects are exploration, credit assignment and action-sampling noise. Classification has none of them. A classifier is a policy whose expected reward, its expected accuracy, is the probability it assigns to the correct label, and because that label is known, the policy gradient is exact and smooth. Yet exact policy gradient loses to cross-
entropy, even on expected accuracy. The exact gradient is myopic: it values an update only by what it buys now, but each update also sets where the next one starts, so an update's value depends on how much learning remains. Viewed this way, cross-
entropy is patient accuracy, the total error an example would pay if its log-odds rose at unit speed forever, while exact policy gradient is the zero-horizon limit. Truncating this total at the learning that remains yields the horizon loss, a one-line change that moves from cross-
entropy toward exact policy gradient as training runs out. In a simple allocation model, it provably escapes the trap that catches each endpoint. On MNIST and on ImageNet with ResNet-50, ResNet-101 and ViT-S/16, the horizon loss improves top-1 accuracy over cross-
entropy at a flat learning rate, and the gain grows with label noise.
Read the full abstract ▾
Statistics Theory
Bayesian Operator Learning: Posterior Existence and Convergence of Point Estimates for Gaussian Priors
Niklas Reinhardt and Jakob Zech
We develop a
Bayesian framework for learning nonlinear operators between infinite-dimensional spaces. Given a map $g_0:\mathcal{X}\to\mathcal{Y}$ between separable
Hilbert spaces, we study the recovery of $g_0$ from $n\in\mathbb{N}$ noisy input-output pairs $(\boldsymbol{X},\boldsymbol{Z})=(X_i,Z_i)_{i=1}^n$ with $Z_i= g_0 (X_i ) + E_i$. Here the $X_i\in\mathcal{X}$ are randomly drawn 'design' points in a compact subset of $\mathcal X$, and the $E_i$ are assumed to be i.i.d. draws from a Gaussian white noise process indexed by $\mathcal{Y}$. For any 'operator-valued' prior $\mathbb{P}_G$ supported on the space of continuous operators, we show existence of the posterior $\mathbb P_{G|(\boldsymbol{X},\boldsymbol{Z})}$ as a regular conditional distribution, and provide a characterization of its Radon-Nikodym derivative. For Gaussian priors, we establish algebraic (in the sample size $n$) convergence rates for the posterior mean towards the ground truth; this corresponds to a ridge regularized kernel
estimator. Moreover, we show that the posterior mean is minimax optimal (up to logarithmic factors) over hyperrectangles when the smoothness of the prior matches that of the ground truth. To illustrate the applicability of our analysis, we derive explicit learning rates for the Darcy flow solution operator.
Read the full abstract ▾
Representation Theory · Cross-listed from quant-ph
Lie Algebraic Uncertainty Relations
Xiaoli Hu, Naihuan Jing, Jian Zhang et al. (+1 more)
Uncertainty relations impose fundamental constraints on
quantum observables, yet optimal bounds are needed to determine their incompatibility through the minimum attainable uncertainty. Here we introduce a covariance-
matrix formulation from which infinitely many uncertainty relations follow, encompassing Hermitian observables and non-Hermitian operators and recovering the variance sum as a special case. Within this family, a basis-independent uncertainty for simple and semisimple Lie
algebras admits an exact solution: its optimal state-independent bound is an explicit pairing of root system with the highest weight of the representation. The minimum is attained by a highest-weight state, replacing a search over
quantum states with a calculation in representation theory. A complementary result establishes that uncertainty is constant within each weight space, yielding a conservation law. The same commutation relations can therefore support distinct uncertainty limits, depending on their realization on the state space. By rendering these limits analytically accessible, the framework turns representation theory into a tool for quantifying
quantum incompatibility and may help establish the boundary between attainable and impossible tasks in
quantum theory.
Read the full abstract ▾
All authors Xiaoli Hu, Naihuan Jing, Jian Zhang, Yunlong Xiao
Optimization and Control · Cross-listed from cs.LG
On the Convergence of Success Conditioning for Policy Optimization
Matthew Brun and Xu Andy Sun
Success conditioning is a strategy for improving decision-making policies in
stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, such a policy is obtained within $\mathcal{O}(\log(1/\varepsilon))$ iterations.
Read the full abstract ▾
Optimization and Control
The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
Wendao Wu, Haihan Zhang, Chenheng Zhang et al. (+5 more)
We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex–strongly-convex
stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(p\epsilon^{-4-2/p})$ (Chen et al., 2026), but necessity of the exponent $4+2/p$ was open. We prove matching upper and lower bounds $\Theta_p(\epsilon^{-4-2/p})$ under fixed nondegenerate regularity budgets, with constants allowed to depend on $p$. The lower bound holds for unrestricted randomized
algorithms under a fixed sample budget, allows dimension to grow with accuracy, and preserves global unbiasedness and all prescribed lower-variable smoothness bounds, even with a scalar lower variable and exact upper gradients. We further characterize the minimax fixed-budget complexity under $L_j=M\Lambda^j(j!)^\beta$ for $j\ge3$: $Q_{p,\beta}^*(\epsilon)=\Theta\left(\epsilon^{-4}\left[\inf_{1\le r\le p,,r\in\mathbb N} r^\beta\epsilon^{-1/r}\right]^2\right)$, for $p\in\mathbb N\cup{\infty}$, with constants independent of $p$. At infinite order, this gives $\Theta(\epsilon^{-4})$ for $\beta=0$ and $\Theta(\epsilon^{-4}\log^2(1/\epsilon))$ for $\beta=1$. A gradient-difference method with weighted independent batches attains these bounds uniformly in order. Thus quantitative smoothness yields precise gains, whereas qualitative analyticity alone still permits $\Theta(\epsilon^{-6})$ complexity.
Read the full abstract ▾
All authors Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin
Optimization and Control
Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization
Haihan Zhang, Wendao Wu, Chenheng Zhang et al. (+5 more)
We characterize the optimal accuracy dependence for smooth nonconvex–strongly-convex bilevel optimization with
stochastic first-order oracles. For globally unbiased fresh-gradient observations with bounded variance, we prove an $\Omega(\epsilon^{-6})$ lower bound matching the accuracy exponent of existing upper bounds. We consider globally Lipschitz gradients, a bounded upper gradient in the lower variable, and Lipschitz lower Hessian blocks, with target $\mathbb{E}|\nabla F(\widehat{x})|\le\epsilon$. Let $L$ be the common first-order scale, $\mu$ the lower strong-convexity modulus, $\rho$ the lower Hessian-variation budget, $\kappa=L/\mu$, and $\chi=1+\rho/\mu$. For $\rho\gtrsim\mu$, $\chi\lesssim\kappa$, sufficiently high accuracy, and sufficiently large dimension, we establish $\Omega\left(L\kappa^2\Delta\epsilon^{-2}+L^3\chi^2\kappa^8\sigma_g^2\Delta\epsilon^{-6}\right)$, where $\Delta$ is the initial gap budget and $\sigma_g^2$ is the lower-gradient variance budget. The bound holds over full Euclidean spaces against arbitrary randomized adaptive
algorithms, even when every sample is the gradient of a scalar function. In the common-scale regime $\rho=\Theta(L)$, the leading
stochastic term has condition-number dependence $\kappa^{10}$, compared with the achievable $\kappa^{11}$ dependence. The proof embeds a sequential hard objective into an exact lower response while preserving global regularity and finite gap. A multiscale decomposition limits the gradient signal carrying each new direction, yielding the required sample complexity. We complement this lower bound with a frozen-linear-tilt
estimator whose bias is proportional to lower Hessian variation. Its analysis makes this structural dependence explicit and yields matching leading rates in the specified
curvature-controlled and small-gap regimes.
Read the full abstract ▾
All authors Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin
Information Theory · Cross-listed from quant-ph
Entanglement of purification for Werner states: canonical purification and nonadditivity
Zahra Baghali Khanian and Amir-Reza Negari
We prove that the von Neumann
entanglement of purification is nonadditive. For two-
qubit Werner states $W(f)$ with singlet weight $1/64\le f\le1/4$, we show that canonical purification is globally optimal: its
entanglement, also known as reflected
entropy, gives the exact
entanglement of purification. In contrast, the regularized
entanglement of purification lies strictly below the reflected
entropy for $0<f<f_\ast$, where $f_\ast\approx0.017$. Together, these results establish nonadditivity throughout $1/64\le f<f_\ast$. Our canonical-optimality proof generalizes the proof in [1], which established Rényi nonadditivity for $0\le\alpha<1$ using classical two-
qubit states. We thus resolve the additivity question at $\alpha=1$. Remarkably, nonadditivity is again witnessed by separable states and no
entanglement in the underlying states is required.
Read the full abstract ▾
Mathematical Physics · Cross-listed from quant-ph
Discriminating Lindbladian Dynamics
Robert Salzmann, Ludovico Lami, Martin B. Plenio et al. (+1 more)
The fundamental task of
quantum hypothesis testing, which consists in discriminating
quantum objects, has been extensively studied for
quantum states and channels. Here, we investigate the fundamental limits of discriminating an arbitrary pair of
quantum Markovian dynamics generated by Lindbladians, focusing on the roles of total exposure time and temporal resolution. We allow adaptive choices of
evolution durations and arbitrary instantaneous controls between them. We characterise the optimal type-II error exponent (Stein exponent) as the largest instantaneous increase of
quantum relative
entropy, and give an algebraic criterion for its finiteness in terms of the Lindbladians. Remarkably, an infinite exponent is equivalent to a vanishing type-II error probability at sufficiently large finite total time, for every positive type-I tolerance. While some dynamics admit a finite protocol with zero type-II error, others require increasingly fine temporal control. For the latter, the error vanishes as the minimum allowed
evolution duration, or resolution time, tends to zero at fixed sufficiently large total time, but remains bounded away from zero at every fixed positive resolution time. We achieve this using
quantum Zeno protocols, establishing temporal resolution as a resource for discrimination. When the null hypothesis is the identity
semigroup, an infinite asymptotic error exponent has a stronger consequence: at a fixed finite total exposure time, the type-II error can be made arbitrarily small while keeping the type-I error exactly zero. This is impossible in the corresponding classical setting. Discriminating the identity
semigroup from generalised amplitude damping on a
qubit provides examples of all three regimes: a finite asymptotic error exponent, zero type-II error attainable at positive resolution time, and vanishing type-II error requiring the resolution time to tend to zero.
Read the full abstract ▾
All authors Robert Salzmann, Ludovico Lami, Martin B. Plenio, Susana F. Huelga
Logic
On differentiability in weakly o-minimal expansions of fields
Juan Pablo Acosta, Yatir Halevi, Assaf Hasson et al. (+2 more)
We show that every definable function in a weakly o-minimal expansion of a field $K$ is generically differentiable, where the derivative takes values in the Cauchy completion of $K$, i.e. it is a definable nonvaluational cut. As a consequence, every definable field is definably isomorphic to either $K$ or its algebraic closure.
Read the full abstract ▾
All authors Juan Pablo Acosta, Yatir Halevi, Assaf Hasson, Will Johnson, Ya'acov Peterzil
Dynamical Systems
Sturmian beta-shifts do not have typical periodic optimization
Wen Huang, Oliver Jenkinson, Leiye Xu et al. (+1 more)
A shift space is said to have typical periodic optimization (TPO) if the set of Lipschitz functions whose unique maximizing measure is supported on a periodic orbit contains an open dense subset of the space of Lipschitz functions. We show that beta-shifts whose lexicographically largest point is a Sturmian sequence do not have TPO: on each such beta-shift there is a non-empty open set of Lipschitz functions, all of which have the Sturmian measure as their unique maximizing measure. These are the first known examples of beta-shifts without TPO, and, since they have the specification property, the first known examples of shift spaces with specification but without TPO. The corresponding beta-transformations do not have TPO in any space of Hölder functions on the interval. The main ingredient in the proof of these results is a
rigidity property of Sturmian subshifts: modulo constants and Lipschitz coboundaries, the space of Lipschitz functions on such a subshift is one-dimensional.
Read the full abstract ▾
All authors Wen Huang, Oliver Jenkinson, Leiye Xu, Yiwei Zhang
Analysis of PDEs
Quantitative uniqueness for bi-Laplace equations with $C^2$ lower-order coefficients
Zhiwei Wang
We study quantitative unique continuation for bi-Laplace equations \[ \Delta^2u+W(x)\Delta u+V(x)\cdot\nabla u=0 \] with $C^2$ lower-order coefficients. Using the weighted-frequency function, we establish an $L^\infty$ three-ball inequality whose exponential factor has coefficient dependence $\|W\|_{C^2}^{1/2}+\|V\|_{C^2}^{1/3}$. Under some normalization, we obtain a vanishing-order bound of size $C(\|W\|_{C^2}^{1/2}+\|V\|_{C^2}^{1/3})$.
Read the full abstract ▾
Combinatorics
Signed seeds and G-gradings on cluster algebras
Lauren Williams and Alan Yan
The theory of cluster
algebras is closely connected to the theory of total positivity; indeed, the desire to better understand total positivity was one of the main motivations for Fomin and Zelevinsky's introduction of cluster
algebras [arXiv:math/0104151]. In particular, any cluster variety whose coordinate ring has a cluster structure has a natural notion of positive part: the subset of the variety where all cluster variables are positive. In this paper, we explain that there are other signed
cells contained in cluster varieties that are equally natural from a cluster-theoretic point of view. These come from signed seeds, which can be thought of as a $\mathbb{Z}/2\mathbb{Z}$-grading on cluster variables, and which were introduced in [arXiv:2310.17727] in the context of the amplituhedron. More generally, given any abelian group $G$, we introduce the notion of a $G$-graded seed for a cluster
algebra, which is a way of assigning elements of $G$ to each cluster variable which is compatible with the cluster structure. When $G$ is the multiplicative group $\{-1, 1\}$, this recovers the above notion of signed seed; when $G = \mathbb{C}^*$, this recovers the notion of cluster
automorphism group [GSV10] or cluster dilation group [arXiv:2603.17890]; and when $G = \mathbb{Z}^d$, this recovers the notion of graded cluster
algebra studied by Grabowski-Launois [arXiv:1301.2133], Grabowski [arXiv:1309.6170] and Gekhtman-Shapiro-Vainshtein [GSV10, Section 5.2] (which had previously appeared in special cases in work of Fomin-Zelevinsky [arXiv:math/0602259]). The examples we study include the space of square
matrices, symmetric
matrices, skew-symmetric
matrices, positroid varieties, and amplituhedron tiles. We also connect this notion to tropical mutation when $G = \mathbb{R}$ or $\mathbb{Z}$.
Read the full abstract ▾
Combinatorics
Counting Hamiltonian Sturm permutations: generating functions and Gaussian distributions
Bernold Fiedler and Carlos Rocha
Our combinatorial analysis is motivated by the PDE dynamics \begin{equation} \mathbf{u_t} = \mathbf{u_{xx}} + \mathbf{g}(\mathbf{u}),\qquad 0<\mathbf{x}<1, \end{equation} of solutions $\mathbf{u}=\mathbf{u}(\mathbf{t},\mathbf{x}),\ \mathbf{t}\geq 0$, under Neumann boundary conditions. For dissipative nondegenerate nonlinearities $\mathbf{g}$, the global attractors $\mathcal{A}=\mathcal{A}_\mathbf{g}$ of the PDE can then be classified by the orderings of their $2n+1$
equilibria $\mathbf{v}$ at the boundaries $\mathbf{x}=0,1$. We encode the boundary orders as
Hamiltonian Sturm permutations. The name ”Sturm” refers to nodal properties of PDE solutions $\mathbf{u}(\mathbf{t},\mathbf{x})$. ”
Hamiltonian” refers to the second order pendulum ODE for
equilibria $\mathbf{v}(\mathbf{x})$: \begin{equation} 0 = \mathbf{v_{xx}} + \mathbf{g}(\mathbf{v}). \end{equation} We determine the generating function $a(z)=\sum_n a_nz^n$ for the counts $a_n$ of
Hamiltonian Sturm permutations. For $n\rightarrow\infty$, this provides explicit asymptotics of $a_n$. We refine these counts as $a_n=\sum b_{rq}$. Here $b_{rq}$ counts
Hamiltonian Sturm permutations with $2r+1$ spatially homogeneous
equilibria and $2q$ spatially non-homogeneous
equilibria, such that $r+q=n$. We also determine the explicit generating function $b(x,y)=\sum_{r,q} b_{rq}x^ry^q$. This implies asymptotically Gaussian distributions of the probabilities $p_{nr}=b_{rq}/a_n$ with $r+q=n$, asymptotically for large $n$. We derive asymptotics for means and variances, with error estimates of order $1/n$. All asymptotics are based on work by Flajolet and Sedgewick. We conclude with numerical illustrations and remarks on nonlinearities $\mathbf{g}(\mathbf{u},\mathbf{u_x})$ under periodic boundary conditions $\mathbf{x}\in\mathbb{S}^1=\mathbb{R}/2\mathbb{Z}$, where rotating waves arise.
Read the full abstract ▾