Comments on the recent improvements of the MRRW bounds

• URL: http://arxiv.org/abs/2609.01860v1
• Date: Tue, 01 Sep 2026 20:43:23 GMT
• Title: Comments on the recent improvements of the MRRW bounds
• Abstract summary: We present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.<n>We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
• Score: 59.04174294928297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The asymptotic McEliece--Rodemich--Rumsey--Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.

Related papers

• Consistent Geometric Deep Learning via Hilbert Bundles and Cellular Sheaves [68.683840670745]
  We introduce a novel convolutional learning framework for possibly infinite-dimensional signals supported on a manifold.<n>We make HilbNets and, more generally, the convolution operation, implementable via a two-stage sampling procedure.<n>Our results broaden the scope of geometric learning as a whole by lifting classical Laplacian-based frameworks to settings where the signal at each point lives in its own Hilbert space.
  arXiv  Detail & Related papers  (2026-05-07T15:08:58Z)
• Qudit Twisted-Torus Codes in the Bivariate Bicycle Framework [0.0]
  We study finite-length qudit quantum low-density parity-check (LDPC) codes from translation-invariant CSS constructions on two-dimensional tori with twisted boundary conditions.<n>For the finite sizes explored, twisted-torus qudit constructions typically achieve larger distances than their untwisted counterparts.
  arXiv  Detail & Related papers  (2026-02-04T11:15:51Z)
• BRIDGE: Building Representations In Domain Guided Program Verification [67.36686119518441]
  BRIDGE decomposes verification into three interconnected domains: Code, Specifications, and Proofs.<n>We show that this approach substantially improves both accuracy and efficiency beyond standard error feedback methods.
  arXiv  Detail & Related papers  (2025-11-26T06:39:19Z)
• A Note on Clifford Stabilizer Codes for Ising Anyons [0.0]
  We provide a streamlined elaboration on existing ideas that link Ising anyon (or equivalently, Majorana) stabilizer codes to certain classes of binary classical codes.
  arXiv  Detail & Related papers  (2025-03-11T06:17:51Z)
• Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
  In this paper, we aim to characterize the gates of quantum Reed-Muller (RM) codes by exploiting the well-studied properties of their classical counterparts. A set of stabilizer generators for a RM code can be described via $X$ and $Z$ operators acting on subcubes of particular dimensions.
  arXiv  Detail & Related papers  (2024-10-10T04:07:24Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Geometrically Local Quantum and Classical Codes from Subdivision [10.357542321841887]
  A geometrically local quantum code is an error correcting code situated within $mathbbRD$, where the checks only act on qubits within a fixed spatial distance. Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure.
  arXiv  Detail & Related papers  (2023-09-28T02:12:38Z)
• New and improved bounds on the contextuality degree of multi-qubit configurations [0.0699049312989311]
  We present algorithms and a C code to reveal quantum contextuality and evaluate the contextuality degree. The paper first describes the algorithms and the C code. Then it illustrates its power on a number of subspaces of symplectic polar spaces whose rank ranges from 2 to 7. The most interesting new results include: (i) non-contextuality of configurations whose contexts are subspaces of dimension 2 and higher, (ii) non-existence of negative subspaces of dimension 3 and higher.
  arXiv  Detail & Related papers  (2023-05-17T14:02:57Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. We show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, 2012] (QMA(2)-complete for 1/poly promise gap)
  arXiv  Detail & Related papers  (2022-06-10T17:35:10Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
  arXiv  Detail & Related papers  (2020-02-05T03:09:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.