Discrepancy for Random Linear Codes

• URL: http://arxiv.org/abs/2606.24471v1
• Date: Tue, 23 Jun 2026 12:01:54 GMT
• Title: Discrepancy for Random Linear Codes
• Abstract summary: We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes.<n>First, random linear codes match unstructured random codes for list-decoding from errors above capacity.<n>Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity.
• Score: 10.105438043325357
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\subseteq\mathbb F_q^n$ is a random linear code of rate $1-\frac1n\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\le \ell\le q-1$, a random linear code of rate $1-\log_q\ell+ε$ satisfies, with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\times\cdots\times S_n$ with $|S_i|=\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\mathbb F_q$ with privacy threshold about $n/(2\log q)$ and reconstruction threshold about $5n/(2\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.

Related papers

• Proximity Gaps for Gabidulin Codes and Applications [25.766490264515806]
  We show that every $[n,k,d]$ linear rank-metric code $C$ over $mathbb F_qm$ admits a proximity gap with error $$.<n>For Gabidulin codes, we improve the gap to $(d-1)/(2n)$ with error $10qn-1/qm.<n>These two proximity gaps match those for general linear Hamming-metric codes and Reed-leaved (RS) codes.<n>We then adapt the Ligero-based PCS for ordinarys to obtain a $q$
  arXiv  Detail & Related papers  (2026-09-09T07:45:54Z)
• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee [12.89814955033651]
  Randomized sketch-and-solve algorithms accelerate overconstrained $ell$ regression by replacing the input with a smaller problem.<n>Our sketch yields the $ell_infty$ guarantee with $m=O(-2dlog d)$ rows, uses one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is efficient to apply.
  arXiv  Detail & Related papers  (2026-08-27T02:43:30Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors [3.9657575162895196]
  We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings.<n>For any $ngeq d$ and $epsilongeq d-O(1)$, there is a random $tilde O(d/epsilon2)times n$ matrix $Pi$ with $tilde O(log(d)/epsilon)$ non-zeros per column such that for any $AinmathbbRntimes d
  arXiv  Detail & Related papers  (2025-08-19T19:45:52Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds [0.8594140167290096]
  We show that a randomly chosen linear map over a finite field gives a good hash function in the $ell_infty$ sense. By known bounds from the load balancing literature [RS98], our results are tight and show that linear functions hash as well as trully random function up to a constant factor in the entropy loss.
  arXiv  Detail & Related papers  (2022-04-04T17:21:10Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
  Google's noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24pm0.21)times10-3$. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of quantum circuit.
  arXiv  Detail & Related papers  (2020-05-05T18:01:48Z)

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.