This page collects papers generated with AI (not all prompted by the owner of this page) that are not planned for submission for publication. The papers are deliberately listed without authors. Since they were generated by AI from simple prompts, leaving the author line blank feels like the clearest and most honest reflection of how they were made. The content here is less thoroughly verified and polished than published work, though the owner of this page is fairly confident about the correctness of each document.
Abstract. We show that Myerson regularity is not preserved by convolution, even for two independent identically distributed bounded nonnegative summands. This gives a negative answer to the second future direction posed by Beyhaghi, Cai, Feng, Li, and Weinberg in Competition Complexity in Multi-Item Auctions: Beyond VCG and Regularity, which asks whether sums of regular distributions remain regular even in the i.i.d. setting. We give an explicit common marginal supported on [0, 1] whose survival function equals a/(a + x) on [0, 49/100] and B(1 − x) on [49/100, 1], where a = 1/50 and B = 200/2601. Its virtual value is constant on the first interval and increasing on the second, so the marginal is regular. For the sum of two independent copies, a direct local calculation of the convolution density and survival function shows that its virtual value has a strictly negative right derivative at the interior point 1. Hence the convolution is not regular.
Abstract. Can a one-atom Gaussian mixture NPMLE serve as evidence that a sample comes from a single population? Without regularization the answer is no: even under one Gaussian component, the fitted support diverges. We study whether a small variance inflation prevents this spurious support growth. The observations are i.i.d. N(0, 1 − εn), while the fitted location mixture uses unit-variance Gaussian components. If εn = n−rn and rn → r, the one-atom probability converges to a phase curve p(r). The curve is continuous, equals one at r = 0, is strictly decreasing on (0, 1/4), and vanishes for r ≥ 1/4. We identify its behavior at both endpoints; the upper endpoint is governed by the persistence exponent of a stationary Gaussian process. The limiting curve is defined through two independent compensated Poisson edge fields, which arise from the upper and lower sample extremes. More generally, for r < 1/4 the entire fitted atom count converges to an integer-valued law that depends only on r and varies continuously with r. These limiting counts diverge in probability as r ↑ 1/4, whereas the finite-sample counts are uniformly tight whenever lim sup rn < 1/4.
Abstract. Can a fitted Gaussian mixture distinguish a single Gaussian population from latent heterogeneity? Without regularization, the support of the mixture nonparametric maximum likelihood estimator (NPMLE) diverges even when the data come from a single Gaussian component. We ask whether fitting wider Gaussian components regularizes this overfitting. The observations are i.i.d. spherical Gaussians with covariance (1 − εn)Id, while the fitted mixture uses kernels with covariance Id. In dimension two, the transition occurs when εn log n is of constant order. The limiting profile is explicit and combines the largest point of a radial Poisson edge process with the aggregate contribution of observations just inside the edge. For every sequence dn ≥ 3, fixed or growing, a single exact Gamma-quantile normalization describes the transition. When the normalized coordinate tends to s, the NPMLE is unique with probability tending to one, and its support size minus one converges to Pois(e−s). Thus the one-atom probability tends to exp{−e−s}. For fixed d ≥ 3, the Gamma-quantile normalization reduces to εn = (d/2 − 1)(log log n)/log n + O(1/log n). Under a common coupling of the data, the support counts across each critical window converge jointly to a Poisson tail-count process. We also identify the fitted edge masses and, in fixed dimension, their directions.
Abstract. Motivated by distribution testing and empirical Bayes calibration, we ask how sparse a mixture NPMLE can be when the true mixing distribution has fixed finite support. For Gaussian location mixtures in every fixed dimension d, every maximizer has at least c(log n)d/2/log log n atoms with high probability. For Poisson mixtures, the lower bound is c√(log n)/(log log n)3/2. Thus the NPMLE can have diverging support even under a fixed finite mixture.
Abstract. We study directed s–t reachability when an unknown digraph G = (V, E) is accessible only through an outgoing-cut oracle: a query S ⊆ V returns F(S) = |E(S, V ∖ S)|. We give a randomized adaptive algorithm using n3/2 logO(1) n queries and succeeding with probability 1 − n−Ω(1); computation between queries is unrestricted. The conceptual core is a rank-n fractional-orientation linear program. An inverse-polynomially accurate solution induces an implicit threshold digraph having exactly the same zero out-cuts, and hence the same reachability relation, as G. Although the LP has up to Θ(n2) hidden rows, we implement a rank-sensitive Lee–Sidford box-LP method without materializing them. Our main oracle primitive is a spread-independent weighted spectral sparsifier for pair-evaluable conductances, constructed from cut queries by filtered weighted spanners, bundle leverage bounds, and whole-pair sampling. Duplicate hidden copies are kept block-symmetric. Approximate normal solves are handled by the standard stable Lee–Sidford interface, and a public star right inverse keeps every primal update exactly feasible. The result breaks the quadratic query barrier for directed reachability posed in recent work on the cut-query model.
Abstract. We give a short proof of the Bernoulli conjecture. The proof was produced by an internal model at OpenAI.
Abstract. Let A be an n×n real symmetric positive definite matrix of fixed half-bandwidth w, with nonzero integer entries of O(log n) bits and spectrum contained in [n−10, n10]. Given 1 ≤ k ≤ n and dyadic 0 < ε, δ ≤ 1/4, we give a randomized finite-bit algorithm that terminates on every random branch and, with probability at least 1 − 9δ/64 > 1 − δ, returns approximations to the leading k eigenpairs, equivalently the leading symmetric singular triples. Each returned unit vector qi is represented by a nonzero finite dyadic vector yi, interpreted as yi/√(yiTyi), and the nonnegative dyadic eigenvalue estimate σ̂i satisfies ‖Aqi − σ̂iqi‖2 ≤ Cwε‖A‖2, |qiTqj| ≤ Cwε for i ≠ j, and |σ̂i − λi(A)| ≤ Cwε‖A‖2. For Q = [q1 ··· qk], the algorithm also guarantees ‖QTQ − I‖2 ≤ Cwkε. If L = 1 + bε + bδ + ⌈log2(n/(εδ))⌉, where bε and bδ are the canonical binary encoding lengths, its worst-case cost is Ow(nkL3) bit operations, it uses O(nL + kL2) random bits, and its output uses O(nkL) bits. The special case in which ε−1 and δ−1 are polynomial in n and their encodings have O(log n) bits therefore costs Ow(nk log3 n) bit operations. No input eigengap is assumed. The construction uses a finite-bit diagonal perturbation, guarded banded Sturm bisection, and a multishift bank of shifted-inverse polynomial filters.
Abstract. We consider two-step Krylov compression of an arbitrary real matrix A ∈ Rn×n from a standard Gaussian starting vector b ∼ N(0, In). On the event that K2(A, b) is two-dimensional, let Q denote any orthonormal basis of this space; the associated Ritz matrix is QTAQ. For every even n ≥ 4, we construct a real diagonalizable matrix An with ‖An‖2 ≤ 1 + e−n/2 < 3/2 such that K2(An, b) is two-dimensional almost surely and Pr{κV(QTAnQ) ≥ en/5} ≥ 1 − 2e−n/40. For εn = 5e−2n, the same family satisfies E[area Λεn(QTAnQ)] ≥ (1 − 2e−n/40)πe−2n/4. Consequently, for every positive polynomial p, the inequality κV(QTAnQ) ≤ p(n) fails with probability tending to one exponentially fast along the even dimensions. Moreover, for every fixed β > 1 and every positive polynomial p, no upper bound of the form p(n)εβ holds uniformly over all dimensions, inputs, and positive tolerances under this Gaussian starting-vector model.
Abstract. For a nonsingular N-by-N matrix A, let κ̄p(A) be its finite-p averaged condition number. Consider high-accuracy bit-complexity algorithms with running time, up to polylogarithmic factors, either nnz(A)κ̄p(A) or N2κ̄p(A). Assume that dense n-by-n systems of condition number κ = nα require Ω̃(min{nω, n2+α/2}) bit operations on an infinite hard family, and write β(α) = min{ω, 2 + α/2}. Under this hypothesis, no sparsity-sensitive solver of the first type exists for any fixed finite p < max{(β(α) − 1)/α, 1/(2 + α − β(α))}, and no dense-access solver of the second type exists for any fixed p < (β(α) − 2)/(2α). In the mildly conditioned regime 0 < α < 2ω − 4, the dense threshold is p < 1/4, while the sparse threshold includes p < 2/α whenever α < 2. If the dense lower-bound hypothesis holds for arbitrarily small positive α, the sparse result rules out every fixed finite p, and the dense result rules out every fixed p < 1/4. The reduction appends decoupled identity coordinates, optimizes the amount of padding, and recovers the original high-accuracy solution by projection; the output guarantee is constant relative forward error.
Abstract. Let A ∈ Rn×n be symmetric positive definite, let f(x) = (1/2)xTAx − bTx, and set rk = b − Axk. In exact arithmetic, define each restart of length two by minimizing f over xk + span{rk, Ark}. If the initial residual has nonzero spectral projection on at least three distinct eigenspaces of A, then every residual remains nonzero with spectral grade at least three, and the even and odd subsequences of Euclidean-normalized residuals converge to unit vectors ye and yo, respectively. Both limits have spectral grade three or four and form a two-cycle under the normalized monic-quadratic residual map. Moreover, if Ek is the squared A−1-norm of rk, then 0 < Ek+1/Ek ≤ Ek+2/Ek+1 ≤ ((λmax − λmin)/(λmax + λmin))2 < 1, where λmin and λmax are the extreme eigenvalues in the initial cyclic subspace. No simple-spectrum or genericity assumption is imposed. Each restart uses two matrix–vector products and O(n) additional arithmetic operations.
Abstract. This paper gives randomized algorithms for weighted diameter and radius in the quantum CONGEST model. On a connected, undirected n-vertex network of unweighted diameter D and positive polynomially bounded integer edge weights, every vertex outputs a one-sided (1 + o(1)) overestimate, with high probability, in Õ(min{n, n5/6 + √n D}) rounds. Wu and Yao previously obtained Õ(min{n9/10D3/10, n}) rounds for the same problem. For every fixed δ ∈ (0, 1/2), the new bound is polynomially smaller throughout D ≤ n1/2 − δ; when D = Θ(√n), both bounds are Õ(n). The algorithm samples candidate vertices independently of the landmarks used for shortest-path reconstruction. A candidate that is not a landmark is attached as a virtual root to a landmark shortcut graph, and nested distributed quantum optimization selects a good candidate and a good trial.
Abstract. The product test is the optimal two-copy test with perfect completeness for multipartite pure product states. Let PTn(ω) be its largest acceptance probability over n-partite pure states whose squared overlap with the closest product state is ω, with finite local dimensions allowed to vary. Soleimanifar and Wright determined PTn(ω) for ω ≥ 1/2 and asked whether it tends to 1/2 as ω tends to zero. Lovitz and Lowe recently determined the bipartite curve and asked whether it remains extremal in the multipartite low-overlap regime. This paper answers both questions affirmatively. If k = ⌊1/ω⌋, then PTn(ω) = (1/2)(1 + kω2 + (1 − kω)2) for every n ≥ 2 and 0 < ω ≤ 1. Consequently, the soundness tends to 1/2 as ω tends to zero, an extremal state can always be chosen as a bipartite Schmidt state tensored with product factors, and the same formula gives the exact soundness curve of the best two-copy perfect-completeness test. At a high level, a one-party Schmidt-decomposition induction and a sharp 1/2 bound on off-diagonal branches reduce the problem to capped-purity optimization; concatenating the branch probability vectors closes the induction.
Abstract. This paper gives absolute constants δ, c > 0 and a deterministic algorithm which, on arbitrary binary strings s, t of total length n = |s| + |t|, runs in n polylog n time and outputs an explicit common subsequence of length at least (1/2 + δ) LCS(s, t). Equivalently, it is a (2 − c)-approximation, with no assumption that the input lengths or symbol counts agree. He and Li previously showed that, for every fixed ε > 0, some gain δε > 0 over 1/2 is attainable in deterministic n1 + ε time for the same regime. Thus this paper achieves a single absolute gain, independent of the exponent slack ε, in n polylog n time while retaining explicit-subsequence output. Combined with the reduction of Akmal and Vassilevska Williams, the result also gives, for every fixed alphabet size q, a deterministic near-linear-time (1/q + δq)-approximation for arbitrary-length q-ary LCS. The technical core is a promise algorithm for exactly balanced equal-length binary strings. It converts the Guruswami–He–Li string-regularity decomposition into an explicit matching through physical-position grids, robust flag transfer, and an exact stitching dynamic program; trimming, a robust Rubinstein–Song case analysis, and the He–Li reduction then remove the balance and equal-length restrictions.
Abstract. For seminorms N1,...,Nm on Rn, this paper proves that their sum has a uniform (1 ± ε)-sparsifier supported on O(dε−2 log(1/ε)) reweighted summands, where d is the dimension after quotienting by the common kernel. This extends the O(nε−2 log(1/ε)) result of Reis and Rothvoss from one-dimensional summands to arbitrary seminorms, and improves the earlier O(ε−2n log(n/ε)(log n)5/2) general bound of Jambulapati, Lee, Liu, and Sidford by removing its dimension-dependent polylogarithmic losses. Consequently, sums of normalized symmetric submodular functions admit sparsifiers with the same effective-dimension bound, and every weighted hypergraph on n vertices has a cut sparsifier with O((n − κ)ε−2 log(1/ε)) hyperedges, where κ is the number of connected components of its positive-weight 2-section. At a high level, the proof represents seminorms by compact centrally symmetric convex support sets, extends the Reis–Rothvoss coefficient-space argument from sums of segments to arbitrary Minkowski sums using convexity of volume under Minkowski erosion, and applies partial coloring to eliminate a constant fraction of the summands at each step.