This repository was started by Chenghua Liu✉ and Hanyu Li✉ to share AI-generated papers. Papers are listed without authors and are not intended for submission or formal publication. We are reasonably confident in their correctness, though the presentation is less polished than in published work. Lean formalizations were developed primarily with MiMo-V2.6-Pro.
La mer s’avance insensiblement et sans bruit, rien ne semble se casser rien ne bouge l’eau est si loin on l’entend à peine… Pourtant elle finit par entourer la substance rétive…
The sea advances imperceptibly and without a sound; nothing seems to break, nothing moves, the water is so far away that we can scarcely hear it… Yet in the end it surrounds the resistant substance…
For a point null \(P_0\), a growth-optimal e-variable maximises the worst-case expected logarithm over the alternative. We study whether alternatives outside a neighbourhood of the null mean can be reduced to its boundary. In one-dimensional natural exponential families, the two endpoints of an excluded interval suffice. We show that the reduction fails for a minimal regular two-dimensional family on nine points with positive base masses and a circular excluded region in mean space. The infimum of \(D(Q\Vert P_0)\) over finite exterior mixtures is strictly smaller than that over finite boundary mixtures. Remote tilts reconstruct nearly all of the null after mixing, whereas a bounded statistic separates every boundary mixture. For Gaussian location families with fixed positive-definite covariance and null mean zero, we prove boundary reduction for every bounded open neighbourhood of zero. There is a unique Borel probability measure on the boundary minimising the mixture divergence, and its value equals both finite-mixture infima. The mixture likelihood ratio with respect to \(P_0\) is growth-optimal over the full exterior. Gaussian translation makes its expected log likelihood ratio convex in the mean; a first-exit argument then propagates boundary optimality without convexity, connectedness, or smoothness assumptions on the excluded region.
We construct a fixed computable nonnegative even function \(f\) on the integers whose moment \(F_f(x)=\sum_i f(x_i)\) admits a small-space turnstile sketch, but whose approximation by differences of real symmetric Lévy–Khintchine exponents requires large cancellation. The function satisfies \(f(0)=0\) and \(f(k)\in\{1,3\}\) for \(k\ne0\). Its sketch uses space polynomial in inverse relative accuracy and in the logarithms of dimension, final frequency bound, and inverse failure probability. On the integers \([-n,n]\), the cancellation cost of a split \(h=g_+-g_-\) is the least \(\rho\) such that \(g_++g_-\leq\rho f\). Among splits satisfying \(\lvert h-f\rvert\leq\eta f\), the minimum cost is \(\Theta_\eta(\sqrt n)\) for every fixed \(0<\eta<1/6\); an exact finite Fourier split supplies the matching upper bound. This refutes the real-even integer specialization of the controlled-decomposition conjecture of Pettie and Wang (arXiv 2026). The witness uses Rudin–Shapiro signs: their order-\(n\) pairing with the target’s second differences contrasts with the \(O(\sqrt n)\) uniform norm of their cosine polynomial. A positive-measure representation of second differences turns this contrast into a lower bound for the entire symmetric Lévy cone, including arbitrary jump measures and Gaussian parts.
For integers \(n\ge1\) and \(0\le d\le n-1\), we determine the largest integer \(c\) such that every \(n\)-vertex digraph of minimum outdegree at least \(d\) contains a nonempty subdigraph in which every vertex has indegree and outdegree at least \(c\). Digraphs have no loops or parallel arcs; opposite arcs are allowed. The exact guarantee is the least nonnegative integer satisfying \(d(d+1)\le c(2n-c-1)\), and it is best possible even when every vertex of the ambient digraph has outdegree exactly \(d\). Consequently, for each fixed \(0<\alpha<1\), the sharp guarantee under minimum outdegree at least \(\alpha n\), divided by \(n\), converges to \(1-\sqrt{1-\alpha^2}\). This answers the dense extraction question of Grzesik, Rödl, and Volec (Innov. Graph Theory 2025). The proof combines an exact count of the arcs controlled by mixed indegree/outdegree deletion with a matching construction. In the construction, the remaining outdegree demands reduce to an integral flow problem with nested neighborhoods, for which the total capacity condition is also sufficient.
We prove that the maximum number of copies of \(K_{4,4}\) in an \(n\)-vertex \(K_{3,5}\)-free graph is \(\Theta(n^3)\), with the lower bound attained by bipartite graphs. Together with a theorem of Wang, Yang, and Zhou (arXiv 2026), this establishes the cubic order for \(K_{t,t}\) copies in \(K_{3,t+1}\)-free graphs for every fixed \(t\ge4\), answering a question of Pohoata, Tidor, and Yu (arXiv 2026). Our construction uses the degree-four specialization of Wang, Yang, and Zhou’s finite-field point set. Large plane sections are unavoidable at this degree, and reducing all sections to at most four points by point deletion retains only a vanishing proportion of the point set. We instead alter the incidence graph obtained from a random projective pairing. Preliminary edge deletions limit how many exceptional complete bipartite subgraphs contain any remaining edge. A geometric intersection bound then permits local random pruning that eliminates every \(K_{3,5}\) while preserving a constant proportion of the counted \(K_{4,4}\)’s.
Let a unitary oracle prepare a state from a known input, with probability \(p\) of measuring answer \(1\), where \(\lvert p-1/2\rvert\geq\delta\) for a known \(0<\delta<1/2\). We determine the minimax Las Vegas query cost of returning the more likely answer exactly in the transducer model, where each query is charged the squared norm of its queried component. Arbitrary unitary completions and potentially infinite-dimensional separable private space are allowed. With unrestricted controlled access to the oracle and its inverse, the optimum is \(1/(2\delta)\), removing the additive unit in the bound of Belovs and Jeffery (Quantum 2026). If forward queries are confined to the known input ray and inverse queries to the generated-state ray, the optimum is \(1/(1-\sqrt{1-4\delta^2})\), asymptotic to \(1/(2\delta^2)\) as \(\delta\to0\). For every nonzero finite-dimensional oracle workspace, each optimum is attained by a transducer fixed over the whole promised family. The unrestricted construction pulls the answer reflection back to the known input without requiring knowledge of the resulting invariant plane; a four-oracle adversary proves optimality. For restricted access, a signed-Gram characterization proves the optimality of the earlier reciprocal-rescaling construction.
We study relative-entropy approximation of \(k\)-site marginals of exchangeable \(n\)-site laws on a \(d\)-symbol alphabet by mixtures of iid laws. Each one-site factor must lie in a prescribed affine slice of the probability simplex. We assume that, under the exchangeable law, each site’s conditional distribution given the other sites lies in this slice. For \(k\le n/2\), conditioning gives feasible error \(O(k^2\log d/n)\), compared with the unrestricted guarantee \(O(k^2/n)\). We prove that the logarithmic factor is necessary for a bound uniform over affine slices. For even \(n\), we construct examples with \(d=\Theta(n^8)\) and \(k=\lfloor n^{1/4}\rfloor\) whose optimal feasible error is \(\Theta(\log n/\sqrt n)\). Thus the logarithmic separation persists while the error vanishes. The construction places perfect nonsignalling finite-field CHSH boxes on a random perfect matching. An internal matching edge forces an event that is much rarer under every feasible product mixture; its likelihood ratio supplies the logarithmic factor. For the affine slice specifying an input marginal of support size \(s\), a response-table construction gives \(O(sk^2/n)\) error for \(k\le\frac12\lfloor n/s\rfloor\), independently of output-alphabet sizes.
Uniform sampling need not approximate the cost of every candidate median, but it can preserve their relative quality throughout the candidate space. We prove that the worst-case sample complexity of constructing stable Euclidean geometric median coresets by unweighted uniform sampling without replacement is \(\Theta(\varepsilon^{-2})\). For every dataset, \(O(\varepsilon^{-2})\) sampled points suffice in every dimension, with the whole dataset used if it is smaller. For each \(0<\varepsilon<1/4\), with probability at least \(4/5\), every \((1+\varepsilon)\) sample-cost comparison implies a \((1+17\varepsilon)\) population-cost comparison, simultaneously for all candidate pairs. This removes the \(\log(1/\varepsilon)\) factor from the bound of Carmel, Krauthgamer, and Petruschka (APPROX/RANDOM 2026). The matching lower bound holds for the same sampling rule even for distinct points on the line. The proof represents distance as squared Hilbert distance, reducing all comparison errors to linear functionals of one empirical mean error. A finite-population variance bound controls this vector, and the triangle inequality converts the resulting error into a relative guarantee. The argument extends to negative-type metrics and gives the same optimal rate in \(\ell_1^d\), resolving the dimension-independence conjecture of Carmel and Krauthgamer (ICLR 2026).
We give a deterministic fully polynomial-time approximation scheme for partition functions of continuous factor models on the unit cube, with fixed bounds on factor arity, variable occurrence, and Lipschitz constants. For factors \(1\leq\Psi_e\leq e^q\), the algorithm applies when \(3c\sqrt{r-1}\,q<1\) with fixed slack, where \(r\geq2\) bounds the arity and \(c\) bounds occurrence. Under polynomial-time finite-precision value access, it has polynomial bit complexity in the input length and inverse relative accuracy. In particular, it gives polynomial time in the weak-interaction regime of the quasi-polynomial algorithm of Gamarnik and Smedira (Combin. Probab. Comput. 2026). The obstacle to a direct use of zero-free interpolation is numerical: logarithmic-order moments involve logarithmically many coordinates, on which a uniformly fine grid is still too large. We expand each factor in dyadic increments and truncate by total refinement level. Even for overlapping scopes, the common grid has size exponential only in that total level. Combined with Lipschitz decay, this evaluates a local moment of order \(s\) to absolute error \(e^{-as}\), for any fixed \(a>0\), using \(e^{O(s)}\) oracle calls, without mixed derivative assumptions. Stability estimates keep value precision and dyadic coordinate lengths to \(O(\log(n/\varepsilon))\) bits, where \(n\) is the number of variables and \(\varepsilon\) the relative accuracy.
We determine the double-logarithmic Griffiths exponent for the random-field Ising model on \(\mathbb{Z}^d\), \(d\geq2\), at fixed inverse temperature \(\beta\). We consider free-boundary boxes of side order \(n\), independent centered Gaussian fields, and continuous-time heat-bath dynamics with rate-one updates per site. Assume that, along increasing side lengths \(m_j\to\infty\) with \(m_{j+1}/m_j\to1\), the zero-field model admits fixed spin boundary conditions with relaxation time at least \(\exp\{c m_j^{d-1}\}\) for some \(c>0\). For every sufficiently large fixed field variance, the relaxation time and the worst-initial-state total-variation mixing time at error \(1/4\) both have scale \(\exp\{(\log n)^{(d-1)/d+o_{\mathbb{P}_h}(1)}\}\), where \(o_{\mathbb{P}_h}(1)\) denotes convergence to zero in probability over the fields. Under the same pure-model hypothesis, the lower bound holds at every fixed positive variance and attains the power predicted by El Alaoui, Eldan, Gheissari, and Piana (Ann. Probab. 2026). We embed a pure-system slow mode in a weak-field island with an evolving high-field shell. A test function independent of the shell reduces the comparison to equilibrium defect moments, allowing fixed-strength shell fields. The upper bound simulates disorder-adapted block updates by parallel local dynamics and applies censoring. In dimension two, the pure-model hypothesis holds for every \(\beta>\beta_c(2)\).
Strong average self-concordance controls the change in the local norm of a Gaussian step when an arbitrary positive-semidefinite form is added to its proposal precision. For the log-determinant metric \(G=\nabla^2(-\log\det)\) on real symmetric \(q\times q\) positive-definite matrices, we prove this property for every scaled metric \(sG\) with \(s\ge(q+1)/2\). This replaces the quadratic sufficient scale of Kook and Vempala (COLT 2024) by a linear one. The admissible proposal radius depends only on the error tolerance, and the guarantee includes feasibility and a two-sided bound on the change in squared local norm. The auxiliary form can correlate matrix entries. We normalize the proposal to a centered Gaussian matrix with covariance bounded by the identity. A paired-trace estimate of Song and Zhang (arXiv 2026) bounds its quartic trace moment, and Gaussian Poincaré reduces the cubic-trace variance to the same fourth moment. Both are \(O(q^3)\) uniformly over these covariance contractions, yielding the linear scale. We also determine the exact strong self-concordance threshold \((q+1)/2\), making this the optimal scale for requiring strong self-concordance and strong average self-concordance simultaneously.
Every Schmidt rank is a lower bound on CP border rank. We prove a converse uniform in tensor order: if all Schmidt ranks of a complex tensor are at most \(r\), its CP border rank is at most \(\exp(O(r^2\log r))\), independently of the number and dimensions of its factors. This answers the border-rank question of Florido-Llinàs et al. (PRX Quantum 2025) for matrix product states under permutations. Product contractions retain an invertible core of a maximal-rank flattening on boundedly many factors. The other cut constraints force a common matrix-product representation, with noncommutativity confined to boundedly many factors. The remaining factors multiply in a finite-dimensional commutative algebra. Decomposing this algebra into local components, we use nilpotence of their maximal ideals and polarization to express the products through bounded-degree coefficients of product curves. Finite differences give border-rank degenerations of size independent of the product length.
We prove exact universality of symmetric quantum circuits for every finite permutation action on qubits. In the model of arbitrary one-qubit gates and reversible unbounded-fan-in threshold gates, a unitary has a symmetric circuit with clean workspace if and only if it commutes with the given action. Symmetry is required at every layer: each permutation in the given action must admit an extension to all wires that preserves every layer as a set of commuting gates. This answers the arbitrary-group universality question of Castro-Silva, Gur, and Strelchuk (ITCS 2026). For \(n\geq1\) active qubits, the nonuniform construction uses \(O(n8^n)\) gates and \(O(4^n)\) workspace qubits. The main difficulty is that equivariance of a Pauli expansion makes its coefficients constant on orbits, but does not make its individual terms equivariant. We assign a selector wire to each Pauli word and let the group act on these wires. Symmetric preparation and commuting incidence layers then give a block encoding of the target unitary. Exact oblivious amplification removes the normalization using reflections that tolerate permuted workspace, returning all ancillary qubits to their initial zero state and retaining the target global phase.
The shared parameters of the quantum approximate optimization algorithm (QAOA) for MaxCut constrain its standard dynamical Lie algebra to the subalgebra of the multi-angle algebra fixed by graph automorphisms. We show that this symmetry bound can overestimate the standard dimension by an exponential factor. For every \(k\geq7\), we construct a connected asymmetric graph on \(7k\) vertices with maximum degree five for which the symmetry bound is at least \((2048/1985)^k-o(1)\) times the standard dimension. This disproves the universal constant-factor conjecture of Mao, Yuan, Allcock, and Zhang (arXiv 2025). The construction starts from the seven-qubit hidden-symmetry example of Gargiulo, Menta, Giovannetti, and Zeier (arXiv 2026). We express its invariant sector by a product of singlet projectors that leaves one qubit unrestricted. Coupling copies through that qubit preserves an independent projector for each copy, while a rigid tree eliminates graph automorphisms. A general amplification theorem converts these projectors into the exponential dimension gap. The largest irreducible component occupies at most a \((63/64)^k\) fraction of the \(2^{7k-1}\)-dimensional \(+1\) eigenspace of global bit flip. This exponential additive deficit contradicts the universal polynomial-gap formulation of Kazi et al. (PRX Quantum 2025).
We prove that the Boca–Cobeli–Zaharescu map is strongly mixing for normalized Lebesgue measure on the Farey triangle. This answers the mixing question of Athreya and Cheung (Int. Math. Res. Not., 2014), which remained open after Cheung and Quas (arXiv, 2024) established weak mixing. Our main tool is a criterion for weakly mixing transformations whose induced maps on sets of measure tending to one are conjugate to the original transformation by maps converging to the identity. We decompose subsequential limits of graph measures according to the number of extra ordinary iterates needed to complete a fixed number of induced returns. Under a bounded mean-excess hypothesis at each scale, a finite invariant measure built from the positive-excess components forces each such component to be a multiple of the product measure; only the zero-excess component can obstruct mixing. For the BCZ map, we make this remaining mass arbitrarily small by estimating the probability that a long thin rectangle contains no primitive lattice point. The estimate combines a finite prime sieve, exact pairwise independence on an auxiliary torus, and a summable bound for the remaining prime divisors.
We determine exactly when the distribution \(p_t(a,b,c)=[1+t(ab+bc+ca)]/8\), with \(a,b,c\in\{-1,1\}\) and \(0\leq t\leq1\), can be generated by three independent classical sources in a triangle network. It is realizable if and only if \(t\leq t_*\), where \(t_*=0.3621418794\ldots\) is the unique root in \((0.36,0.37)\) of \(3t^4+28t^3+66t^2-36t+3=0\). This proves the optimality of the attaining model of Gisin et al. (Nat. Commun., 2020), also used by da Silva, Pozas-Kerstjens, and Parisio (Phys. Rev. A, 2025) in their conjectured classical boundary. More generally, the same threshold bounds the average pair correlation whenever \(\mathbb{E}(A+B+C)=\mathbb{E}(ABC)=0\), without assuming symmetric responses, identical source laws, or finite source spaces. The proof first reduces this constrained optimization to deterministic responses with at most three values per source. Exact rational inequalities then bound every response-table orbit except the attaining one by \(9/25<t_*\). For the remaining orbit, the constrained stationary equations force identical source laws and determine the quartic. Thus a symmetric optimizer is obtained from the unrestricted problem, rather than assumed. The appendix provides the complete exact-arithmetic program that generates and verifies the finite inequalities, without external data or certificate files.
We prove that a downward-closed language of interval pomsets over a finite alphabet and with a fixed width bound is first-order definable if and only if it is accepted by a finite counter-free higher-dimensional automaton. This establishes the converse conjectured by Erlich, Ledent and Ziemiański (CONCUR, 2026), whose algebraic characterisation identifies first-order definability with recognition by finite aperiodic categories. Given such a recognising category with aperiodicity exponent \(h\) and a width bound \(k\), we effectively construct an automaton of dimension at most \(k\) whose endpoint relations stabilise after \(2k+h\) repetitions. The bound is uniform over all cells and endomorphism pomsets, including those with nonempty interfaces. Rather than completing an algebraic recogniser by adding faces, we use cells consisting of compatible diagrams of lower sets, with face maps given by restriction. A lattice extension criterion characterises paths between prescribed cells, and ordered interfaces allow the relevant repeated pomsets to be factored into fixed boundary pieces and an aperiodic middle factor. We also give an explicit two-dimensional example in which canonical suffix-residual completion introduces a period-two endpoint relation despite the existence of a counter-free realisation.
For every \(n\geq1\), we prove that the space of full-dimensional Delzant polytopes in \(\mathbb R^n\), with the Hausdorff or equivalently the symmetric-difference-volume topology, is an absolute extensor for metrizable spaces. It is therefore an absolute retract and admits a strong deformation retraction onto any prescribed polytope. Its open Hausdorff balls have the same extension property. This answers the fundamental-group question of Pelayo and Santos (Adv. Math., 2025), without restrictions on the normal fans occurring in a continuous family. The proof adapts the extension method of Dugundji (Pacific J. Math., 1951): smooth projective common refinements replace unrestricted convex interpolation, and barycentric subdivision organizes the resulting labels into refinement chains. A boundary estimate independent of the number of labels gives continuity at arbitrary prescribed closed subsets, even when infinitely many normal fans accumulate there. Away from these subsets, the extensions use only finitely many normal fans locally. We also construct continuous Delzant approximations of families of full-dimensional convex bodies with any prescribed positive continuous error, proving that the Delzant locus is homotopy dense in the space of such bodies. The extension theorem applies to the corresponding metric moduli spaces of symplectic toric manifolds with fixed torus and specified moment maps.
We prove that every premodular fusion category over \(\mathbb{C}\) whose Müger center is Tannakian admits a fully faithful braided spherical embedding into a modular fusion category with integral centralizer. The spherical structure is prescribed and need not be positive on the center. Consequently, the embedded simple objects form a union of Galois orbits. This removes the pseudounitarity assumption from the Tannakian-center case of the extension theorem of Johnson–Freyd (arXiv, 2026). The spherical extension step concerns a transparent order-two object with trivial self-braiding and categorical dimension \(-1\): every minimal nondegenerate extension admits a spherical structure extending the given one. We combine fixed-boundary extension theory with the twist constraint of Lacabanne (IMRN, 2021) for nondegenerate pivotal categories, which excludes the only possible nontrivial pivotal slope. Applying this result to a sphericalization yields a modular ambient category with weakly integral centralizer. We then use the sign character comparing its inherited and positive spherical structures to obtain integrality, either directly through a grading or after diagonal condensation. A pointed example shows why the prescribed spherical structure need not extend to a fixed ambient category.
We prove that a Turing degree is high for Scott rank \(\omega_1^{\mathrm{CK}}\) if and only if it is high for isomorphism, answering Question 1 of Franklin, Rossegger, and Turetsky (arXiv, 2026). The result follows from a uniform encoding of arbitrary computable tree path problems by isomorphism problems between computable structures of Scott rank at most \(\omega_1^{\mathrm{CK}}\) in a fixed finite language. The structures are isomorphic exactly when the tree has an infinite path, and paths and isomorphisms are uniformly computable from one another. The key step is a normal form preserving the path problem in which the extendible nodes are computable at each fixed level, with the decision procedure allowed to depend nonuniformly on the level. We obtain this form by coupling a binary path code with numerical decoding bounds: upward closure and Dickson’s lemma give a finite description of extendibility at each level. Applying the classical Boolean group-tree construction then yields computable infinitary definitions of all finite tuple orbits. The construction and both reductions are uniform, while the highness equivalence uses the usual nonuniform convention.
We disprove the conjecture of Su, Xie, and Yu (arXiv, 2026) that the local BPS invariants of every reduced plane curve singularity form a log-concave sequence. The ordinary \(43\)-fold point \(y^{43}-x^{43}=0\) satisfies \(n_{24}^2<n_{23}n_{25}\), and the singularities \(y^{36}-x^{36k}=0\) satisfy \(n_{21}^2<n_{20}n_{22}\) for every integer \(k\geq10\). All BPS coefficients in these examples are strictly positive. The rainbow closures of the corresponding positive braids also give counterexamples to their conjecture for normalized ruling polynomials. Combining the Hilbert–HOMFLY and ruling identities with type-\(A\) Hecke character theory, we express the BPS polynomial of \(y^r-x^{rk}=0\) as the canonical trace of a full-twist power. For fixed \(r\) and \(h\), the coefficient \(n_h\) is polynomial in \(u=k(k+1)\), of degree at most \(h\); its coefficient of \(u^h\) is the number of length-\(2h\) transposition walks from the identity to itself in \(S_r\), divided by \((2h)!\). These leading coefficients explain the eventual failure of log-concavity, while an exact polynomial sign certificate gives the explicit range \(k\geq10\). The finite integer and rational computations certifying both results are included in full.
We study estimation of the pseudo-spectral gap of a finite ergodic Markov chain from a single trajectory. For a known state space of size \(d\ge2\), stationary minimum \(\pi_\star\), and pseudo-spectral gap \(\gamma_{\mathrm{ps}}\), we construct an estimator with relative error \(\varepsilon\in(0,1/2)\) and confidence \(1-\delta\) using \(O((\pi_\star\gamma_{\mathrm{ps}}\varepsilon^2)^{-1} \log(d/(\delta\pi_\star\gamma_{\mathrm{ps}})))\) transitions. The guarantee holds from every initial distribution, and the estimator requires no knowledge of the stationary law or gap. This extends the constant-factor inverse-gap bound of Wolfer and Kontorovich (Ann. Appl. Probab., 2024) to arbitrary relative precision, improving their general-precision dependence from \(\gamma_{\mathrm{ps}}^{-3}\) to \(\gamma_{\mathrm{ps}}^{-1}\). On classes with \(\pi_\star\ge p\) and \(\gamma_{\mathrm{ps}}\ge g\), where \(0<p\le1/d\) and \(0<g\le1/8\), we prove a matching lower bound \(\Omega((pg\varepsilon^2)^{-1})\) at constant confidence, even for reversible chains with a common known stationary law. The main estimate compares a bipartite Laplacian with its empirical counterpart relative to the Laplacian plus a regularization term. Positive semidefinite edge matrices allow the martingale variance to be controlled by occupation counts. Separate incoming and outgoing normalization ensures empirical contractivity, so the lagged estimates can be combined without additional inverse-gap factors.
We prove that non-signaling assistance attains the sphere-packing error exponent for every finite classical–quantum channel with full-rank output states, at every strictly positive rate below the Holevo capacity. Thus, in this setting, the auxiliary noiseless bit in the activated reliability theorem of Oufkir, Tomamichel, and Berta (Lett. Math. Phys., 2026) is unnecessary. The main result is a dimension-independent one-shot comparison: for every finite classical–quantum channel \(V\) and integer \(M\geq2\), \(\varepsilon_{\mathrm{MC}}(M,V)\leq\varepsilon_{\mathrm{NS}}(M,V)\leq\varepsilon_{\mathrm{MC}}(M+6,V)\), where \(\varepsilon_{\mathrm{NS}}\) is the optimal non-signaling error and \(\varepsilon_{\mathrm{MC}}\) its meta-converse relaxation. We obtain the upper bound by completing the operator normalization of a relaxed decoding family while preserving its input distribution and increasing every effect in the positive-semidefinite order. The correction is determined by a linear map close to the identity; the message-count slack gives spectral margins that keep the solution between zero and the identity. Unlike an additive error estimate, this comparison preserves exponentially small errors. The one-shot result also holds for singular output states. For full-rank channels, continuity of the sphere-packing function transfers the known meta-converse exponent to non-signaling coding and yields ordinary limits for both assisted models with exactly \(\lceil2^{nR}\rceil\) messages.
We construct an element of exact order six in the second integral homology of the ordered configuration space of four points on a finite graph. This disproves the torsion-freeness conjecture stated by Chettih and Lütgehetmann (Algebr. Geom. Topol., 2018). Twice the constructed class has order three, giving an affirmative answer, in the ordered setting, to the question of odd torsion highlighted by Mamun, Nalikka, and Ramos (arXiv, 2026). The graph has six vertices and thirteen edges, or eight vertices and fifteen edges in a homeomorphic simple presentation. The proof uses an integral cycle \(z\), an integral chain with boundary \(6z\), and a cocycle modulo six evaluating to one on \(z\). These identities establish the exact order without a full homology computation. We construct the certificate by unit cancellation over \(\mathbb Z[S_4]\) and then over \(\mathbb Z\), followed by Bézout identities and explicit lifting to the original cubical complex. A complete program in the appendix generates the certificate from the graph and checks all identities using exact arithmetic, including the cocycle condition on every labelled three-dimensional cube.
We determine the bounded-error query complexity of uniformity testing when access to a distribution is provided by a preparation unitary with arbitrary garbage. For every integer \(d\ge2\) and \(0<\varepsilon<1/2\), distinguishing the uniform distribution on \(d\) labels from distributions at total-variation distance greater than \(\varepsilon\) requires \(\Omega(\min\{d^{1/3}\varepsilon^{-4/3},\sqrt d/\varepsilon\})\) queries. This matches the upper bound of Canonne, Kothari, and O’Donnell (TQC, 2025) and remains valid when inverse and controlled queries are allowed. In particular, it determines the joint dependence on dimension and accuracy, including the transition at \(\varepsilon=d^{-1/2}\). The main obstacle is to control information obtained from the action of the entire unitary, not merely from the state it prepares. We construct reflection oracles with finite-dimensional, phase-randomized garbage and compare the uniform distribution with a symmetric Dirichlet prior. Our adversary operator combines a quadratic cutoff on label degrees with normalized Dirichlet moments. An exact posterior covariance identity controls the radial directions orthogonal to these moment vectors. The resulting full-operator norm estimate yields both branches of the lower bound.
We prove that polynomial-time quantum catalytic logspace computations with intermediate measurements and resets can be simulated using one clean qubit and otherwise maximally mixed qubits. The source may use logarithmic-space classical control and polynomially many catalytic qubits, whose arbitrary unknown state must be restored exactly, including its correlations with an inaccessible reference. The simulator has polynomial size, is deterministic-logspace-uniform, and is unitary until a final measurement with inverse-polynomial signed acceptance bias. Thus \(\mathsf{BQCL}\subseteq\mathsf{DQC1}\) under this bias convention, extending the unitary containment of Buhrman et al. (TQC, 2025). The main difficulty is to avoid storing a polynomial-length measurement history in initialized memory. We express the source’s acceptance bias as a normalized trace involving the inverse of a channel-history matrix. Although the history matrix can be poorly conditioned, complete positivity bounds the Frobenius norm of its inverse. A nuclear-norm regularization estimate then controls the required trace with no dependence on the exponential catalyst dimension. We implement the resulting bounded spectral filter by coherent phase estimation and extract its relevant block through a reflected unitary trace test. The logarithmic auxiliary space is included in the maximally mixed input at only an inverse-polynomial loss in bias.
We prove copy lower bounds for estimating a rank-at-most-\(r\) quantum state in dimension \(d\) under two chi-squared losses. For Bures chi-squared divergence, error at most \(\varepsilon\) with success probability at least \(2/3\) requires \(\Omega(\sqrt r\,d^{3/2}/\varepsilon)\) copies with collective measurements and \(\Omega(r^{3/2}d^{3/2}/\varepsilon)\) with adaptive one-copy measurements. The bounds hold uniformly for \(d\geq2\), \(1\leq r\leq d\), and \(0<\varepsilon\leq\varepsilon_0\), where \(\varepsilon_0>0\) is universal, and match the upper bounds of Flammia and O’Donnell (Quantum, 2024) up to logarithmic factors. For right-inverse chi-squared divergence, the corresponding rates are \(\Omega(d^2/\varepsilon^2)\) and \(\Omega(rd^2/\varepsilon^2)\); we give upper bounds matching exactly in the collective model and up to a logarithmic factor in the one-copy model at constant confidence. The lower bounds quantify how much output mass must be allocated outside an uncertain support. We bound the volume of support subspaces compatible with any successful estimate, then use a Sobolev inequality to relate posterior concentration on these sets to the Fisher information available from measurements. For pure states, the usual covariant measurement with a regularized output attains both collective rates, and we evaluate the exact minimax expected right-inverse chi-squared loss.
We prove that a connected compact complex surface admits at most two holomorphic submersions with connected fibres onto compact curves of genus at least two, up to isomorphism of the bases. In particular, there is no surface with three distinct Kodaira fibrations, answering the existence question posed by Catanese (Jpn. J. Math., 2017). The result also includes isotrivial fibrations and requires no projectivity hypothesis. The proof relates the ramification of a pair of fibrations to an obstruction to a third. Equality of pulled-back hyperbolic metrics forces each reduced ramification component to be smooth and unramified over both bases. Its neighbourhood carries a cyclic action, and its normal bundle has negative degree. A third fibration would produce a holomorphic splitting whose cyclic average is tangent to the ramification curve. When all three fibrations are tangent there, the splittings are meromorphic; averaging and a constant linear combination cancel their principal parts. In either case the resulting regular foliation has the ramification curve as a compact leaf, contradicting the degree-zero condition imposed by its normal connection. The unramified case follows from factorization through a finite product cover.
We prove that integral-current spherical volume is additive on integral homology classes induced from the factors of a free product of countable groups in every dimension at least four. Consequently, it is additive under connected sum of closed connected oriented manifolds in these dimensions, answering the corresponding part of Song’s additivity question (Sém. Théor. Spectr. Géom., 2021–2022). The proof constructs integral transfers indexed by the vertices of the Bass–Serre tree. At each vertex, a shadow map replaces the coordinates in each branch by their norm. The sum of the \(n\)-Jacobians of these maps is at most one for \(n\geq4\). This joint estimate recovers the two factor classes with combined mass no greater than that of the original cycle; separate use of the group retractions does not provide such a bound. To apply the transfers to every competitor in the defining infimum, we establish mass-sharp approximation of cycles by liftable finite-support polyhedral cycles and a relative filling comparison. Both statements hold in the presence of finite stabilizers and preserve integer multiplicities.
We resolve, up to logarithmic factors, the Huber dimension-dependence question posed by Musco, Musco, Woodruff, and Yasuda [14], reducing the rank exponent from \(4-2\sqrt2\) to one. We study fixed-design active regression in the exact-real label-query model: the feature matrix \(A\in\mathbb{R}^{n\times d}\) is known, while an arbitrary response vector is accessible only through coordinate queries. For \(r=\operatorname{rank}(A)\), our randomized nonadaptive algorithm queries \(\min\{n,\widetilde O(r/\varepsilon^2)\}\) labels and, with probability at least \(0.99\), returns a \((1+\varepsilon)\)-approximation to the square root of the empirical Huber loss. All query locations are fixed before any label is read. For every admissible pool size and rank, and \(0<\varepsilon\leq1/800\), we construct a fixed rank-\(r\) design on which every adaptive randomized algorithm with the same worst-case guarantee needs \(\Omega(\min\{n,r/\varepsilon^2\})\) labels in worst-case expectation. Thus label complexity is jointly optimal in pool size, rank, and accuracy up to logarithmic factors in this range. The guarantee requires no distributional or noise assumptions and includes zero-optimum instances. The key ingredient is a centered affine transfer lemma: design-only multiscale scores preserve the objective increments needed to locate the minimizer after an independent constant-factor pilot. This overcomes the hidden-label dependence of standard affine sparsification and turns near-linear design sparsification into a near-optimal active algorithm.
We establish the \(\Theta(\sqrt T)\) minimax rate of calibration distance in sequential binary prediction under simultaneous play. This closes the lower-bound exponent gap posed by Qiao and Zheng [13], from \(\Omega(T^{1/3})\) to \(\Omega(\sqrt T)\), for behavioral-kernel randomized forecasters against deterministic past-adaptive adversaries. The adversary may use past forecasts and outcomes but cannot observe the current private forecast. Calibration distance is the total \(\ell_1\) change needed to make the forecast sequence perfectly calibrated in hindsight. For every \(T\geq2\), every such forecaster incurs expected distance at least \(\sqrt T/4320\), while a deterministic algorithm guarantees distance below \(\sqrt T\) on every outcome path. For deterministic forecasters, one fixed outcome string also forces \(\Omega(\sqrt T)\) distance. The upper bound improves the explicit \(2\sqrt T+1\) guarantee of Arunachaleswaran et al. [1]. Its shifted-grid construction admits exact integer optimization and \(O(\log(T+1))\) worst-case time per round in the word-RAM model. Restarting gives a horizon-free bound below \((2+\sqrt2)\sqrt T\) for every prefix, using \(O(\sqrt T)\) memory. The lower bound combines a mean-reverting adversary, Lipschitz calibration witnesses, and martingale fluctuations; averaging then fixes a deterministic adversary. Together, these results determine the minimax exponent in the stated simultaneous-play model. The randomized-forecaster rate against a fixed outcome string remains open.
We establish dimension-free gradient-query bounds without multiplicative logarithmic loss for convex optimization in \(\ell_p\) and Schatten-\(p\) spaces. For fixed \(2\le p<\infty\), \(1<\kappa\le2\), and \(q=p/(p-1)\), suppose the gradient is \((\kappa-1)\)-Hölder continuous from \(\ell_p\) to \(\ell_q\) with constant \(L\), and the initial point lies within distance \(R\) of a minimizer. In the deterministic exact-real oracle model, our accumulative shifted-power regularization method finds \(x\) with \(\left\lVert \nabla f(x)\right\rVert_q\le\varepsilon\) using \(O_{p,\kappa}((LR^{\kappa-1}/\varepsilon)^{p/(\kappa p+\kappa-p)})\) gradient queries when \(0<\varepsilon<LR^{\kappa-1}\), independently of dimension. For Lipschitz gradients, the exponent \(p/(p+2)\) improves the earlier \(2(p-1)/(p+2)\) upper-bound exponent for \(p>2\), addressing the complexity gap identified by Diakonikolas and Guzmán [6]. Contemporaneous work by Pelleriti et al. [18] obtains the same vector rate through accumulated regularization. Our framework also yields a dimension-free Schatten-\(p\) bound for matrix objectives and an accuracy-oblivious checkpoint scheme that retains the target-accuracy rate. The analysis combines minimizer transport, localization, and a summable path bound to convert approximate composite minimization into a final-gradient guarantee. The matrix extension permits exact multicenter proximal computations between oracle calls. We further give a matching minimax comparison under an explicit simultaneous hard-family assumption.
We disprove the conjecture of Davis, Drusvyatskiy, and Jiang [11] that generic convergence of noisy subgradient descent to local minima remains valid without subdifferential regularity. Our counterexample is an explicit two-dimensional, nonnegative, coercive, globally Lipschitz, semialgebraic continuous piecewise-affine objective. For every linear tilt in a nonempty open set, every initialization in a fixed positive-area rectangle, and every \(\gamma\in(1/2,1)\), the noisy Clarke-subgradient iterates with steps \(\alpha_k=(k+8)^{-\gamma}\) converge almost surely to the origin, which is not a local minimizer. The conclusion holds for every admissible Clarke choice made before the current noise is sampled, under conditionally absolutely continuous perturbations bounded coordinatewise by \(10^{-2}\). In particular, a fixed Borel selection with independent and identically distributed uniform disk noise satisfies the original stochastic-approximation assumptions and directly falsifies the conjecture; the open bad-tilt set rules out an almost-everywhere guarantee. The limit is Clarke-critical but not limiting-critical, identifying subdifferential convexification as the obstruction. A shrinking pathwise invariant gives an \(O(\alpha_{k-1})\) convergence envelope. Scaling and separable embedding extend the construction to arbitrary finite uniform-noise radii and every dimension at least two. Thus definability, coercivity, generic linear perturbations, and continuous noise do not suffice to guarantee local-minimum convergence for this recursion.
We answer the question raised by Duchi, Gupta, Jiang, and Sur [5] of replacing the conservative multi-environment jackknife-minmax envelope by corrected jackknife+ endpoint quantiles. Assuming exchangeability across environments and allowing arbitrary within-environment dependence, we characterize exactly when an interval covers at least a \(1-\alpha\) fraction of a new environment with probability at least \(1-\delta\). The solution jointly calibrates the within-environment residual rank and the across-environment endpoint ranks. For equal-size environments, we obtain the exact worst-case failure probability and all valid finite-sample rank pairs, including rounding and ties. The limiting validity budget is \(a/\alpha+2b/\delta\leq1\), where \(a\) and \(b\) are the inner and outer trimming levels. Comparison-graph degree bounds prove validity, and explicit tie-free constructions establish sharpness. For a fixed multiset of unequal environment sizes, an exact Hall-type characterization is computable in quadratic time after sorting when the induced inner ranks and outer rank are positive. In the balanced positive-rank model, asymmetric endpoint ranks offer no minimax improvement, while hidden independent global outer-rank randomization admits an exact tournament-score optimization. We also derive an exact coverage guarantee for an expanded rule under simultaneous on-sample deletion stability and sharp degradation under approximate block exchangeability. Finally, an atomless construction exhibits an arbitrarily large pathwise average-length improvement over jackknife-minmax, demonstrating the potential efficiency gain of calibrated endpoint quantiles.
We resolve the sample-versus-scale tradeoff posed by Arora, Bhattacharyya, Boban, Guruswami, and Kelman [1, Remark 1.9] in robust multivariate polynomial regression, giving scale-independent recovery with optimal degree exponents in an exact-real LP-oracle model. The unknown polynomial \(p\) has degree at most \(d\) in each of \(n\) coordinates. Covariates are i.i.d. product-Chebyshev or uniform, and outlier indicators are mutually independent, independent of the covariates, and have probabilities at most a known \(\rho<1/2\). Inlier errors are bounded by an unknown \(\sigma\); admissible labels may otherwise be adversarial. For \(0<\delta\leq\varepsilon\leq1/2\), our algorithm returns \(\widehat p\) with \(\left\lVert \widehat p-p\right\rVert_\infty\leq(2+\varepsilon)\sigma\) with probability at least \(1-\delta\), using \(O_{n,\rho}((d/\varepsilon)^n\log(d/\delta))\) product-Chebyshev samples or \(O_{n,\rho}((d/\varepsilon)^{2n}\log(d/\delta))\) uniform samples. It does not use \(\sigma\), recovers \(p\) exactly at zero noise, and makes a predetermined \(O_{n,\rho}(1+\log(d/\varepsilon))\) number of LP calls independent of signal magnitude. For fixed dimension, accuracy, positive contamination rate, and success probability, the Chebyshev rate matches the known dependence on \(d\), while the uniform rate has the optimal degree exponent up to an occupancy logarithm. The key ingredient is an arbitrary-representative product-Chebyshev \(L^1\) norming inequality, which enables a Chebyshev-mass-weighted least-absolute-deviations initializer followed by fixed-budget median refinements.
We resolve the linear-rank conjecture of Goujon, Etemadi, and Unser [10] for the expected density of active-candidate switches in random Maxout units. Their quadratic bound counts all pairwise candidate intersections; our analysis counts only intersections visible on the upper envelope. A multiplicity-aware area formula and a sharp visibility inequality give a rank-linear bound along every deterministic finite-length rectifiable path. For a rank-\(K\) unit in the original iid-coordinate model, with weight-coordinate variance \(\sigma_w^2\) and independent bias density bounded by \(B\), we prove \(\mathbb{E}\lambda\leq(K/\sqrt3)B\sigma_w\), where \(\lambda\) is the switch count divided by path length. The fixed-rank coefficient \(K/\sqrt3\) is sharp in the supremal sense, and the optimal universal constant multiplying \((K-1)B\sigma_w\) is \(2/\sqrt3\). The argument extends to weight-dependent conditional bias-density envelopes and independent heterogeneous candidates. For iid copies of a jointly Gaussian weight–bias vector, we derive an exact spherical-length formula whenever score variance is nonzero along the path. Its coefficient is \(c_K=\mathbb{E}\max_{j\leq K}G_j/\sqrt\pi\sim\sqrt{2\log K/\pi}\), where \(G_j\) are iid standard normals. This identifies a sharp contrast between worst-case linear rank dependence and Gaussian square-root-logarithmic growth. The single-unit laws also yield explicit layerwise switch-density bounds for networks with independent layers, linking the resolved conjecture to pathwise complexity in deep random networks.
We develop an anytime posterior-sampling algorithm for finite episodic Markov decision processes with unknown transitions and a separate nested upper-tail CVaR constraint. The method extends the bounded-violation posterior-sampling framework of Kalagarla et al. [18] beyond additive expected-cost constraints to time-consistent tail risk. This extension faces a structural obstruction: when action randomization lies inside CVaR, generic threshold tightening can cause a constant value loss and a strict scalar duality gap. Our solution is a risk bank that sparsely executes minimum-risk policies and uses their sampled-model slack to support untightened constrained planning. With known rewards and costs, model-wise strict feasibility on the support of an arbitrary prior, and exact posterior-sampling and constrained-planning oracles, the learner needs neither a common feasible baseline, the induced feasibility gap, nor the learning horizon. For fixed problem parameters, we prove a \(\widetilde O(\sqrt K)\) upper bound on signed Bayesian reward shortfall after \(K\) episodes, a \(K\)-independent upper bound on expected signed risk-value debt, and a sublinear number of calibration episodes. The comparator is a randomized physical-state Markov policy, and risk control is a signed aggregate guarantee rather than per-episode safety. A support-size-independent CVaR–Hellinger inequality and distorted-occupancy analysis quantify the dependence on tail mass and horizon. We also establish a fixed-\(K\) high-probability certificate, a two-model lower bound attaining the worst-case rare-event risk-debt exponent, and NP-completeness of a one-state planning subclass at every fixed rational tail mass in \((0,1)\).
Han, Jiang, and Wu [11] established the minimax \(\Theta(n^{-1/2})\) one-step Kullback–Leibler (KL) prediction rate for stationary binary renewal processes and left polynomial-time attainment open. We resolve this computational question under only a finite-mean gap law, without a known uniform mean bound, higher-moment condition, or mixing assumption. Our exact multiset dynamic program evaluates a queried prefix continuation mass of a renewal likelihood envelope in \(O(N^4)\) integer operations. With \(N=n+1\), the full batch required by a compression-to-prediction reduction takes \(O(N^5)\) integer operations and polynomial bit time, yielding the optimal \(O(n^{-1/2})\) risk averaged over stationary histories. A computable mixture over occupied gap types retains this worst-case rate and adapts to simpler gap laws: it achieves \(O(s\log n/n)\) for \(s\)-point support, \(O(\log^2 n/n)\) for exponential tails, and \(O(n^{-(1-1/\alpha)}\log n)\) when \(\mu(d)\leq Cd^{-\alpha}\) with \(\alpha>2\). The block assignment also gives \(O(\sqrt N)\) pathwise log-loss regret at a known horizon; dyadic restarting yields a horizon-free polynomial-time predictor with minimax-order \(O(\sqrt N)\) cumulative KL risk. A matching fixed-time lower bound holds even for aperiodic finite-support laws satisfying \(T\leq4\mathbb{E} T\). Finally, we distinguish the genuine stationary conditional on an all-zero history from the ordinary post-renewal hazard, whose substitution changes the integrated minimax risk to the nonvanishing value \(\log2\).
Liu, Ghosal, Balasubramanian, and Pillai [12] conjectured uniform-in-time mean-field convergence for projected Gaussian Stein variational gradient descent (SVGD) beyond Gaussian targets. We give a quantitative affirmative answer for the continuous-time, exact-Gaussian-moment system with kernel \(K_1(x,y)=x^\top y+1\), assuming \(\pi(dx)\propto e^{-V(x)}dx\), \(V\in C^2(\mathbb{R}^d)\), and \(0<\alpha I\preceq\nabla^2V\preceq\beta I\). For Gaussian i.i.d. initialization and every \(N\ge d+1\), the empirical particle law \(\zeta_{N,t}\) and Gaussian mean-field law \(\rho_t\) satisfy \(\mathbb{E}[\sup_{t\ge0}W_2^2(\zeta_{N,t},\rho_t)]\le C r_d(N)\). The asymptotic orders of \(r_d(N)\) are \(N^{-1}\log\log N\), \(N^{-1}(\log N)^2\), and \(N^{-2/d}\) in dimensions one, two, and at least three, respectively; each is sharp in particle number. Thus the time supremum can be placed inside the expectation without losing the Gaussian empirical-measure rate, even at the minimal full-rank sample size. We also obtain high-probability all-time bounds and a last-iterate guarantee to the reverse-KL optimal Gaussian at the same statistical scale. The key deterministic inequality separates initial moment mismatch from the Wasserstein discrepancy of the standardized cloud, using stability in square-root covariance coordinates and exact affine transport. At fixed \(N\), we characterize the discrete limiting cloud: its moments are optimal, but its preserved standardized shape leaves a strictly positive full-law error.