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. 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.