🔢 mathematics

List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

Dit artikel demonstreert dat expliciete tegenvoorbeelden voor lijst-decodeerbaarheid constructief kunnen worden getransformeerd naar codes met een bewezen hoge fout in wederzijdse gecorreleerde overeenstemming, waardoor een directe link wordt gelegd tussen het falen van lijst-decodering en ondergrenzen op deze specifieke foutmetriek voor algebraïsche-geometrie- en Reed-Solomon-codes.

Oorspronkelijke auteurs: Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

Gepubliceerd 2026-07-14

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een detective bent die een groep spionnen (codewoorden) probeert te vangen die proberen langs een beveiligingscontrole (een code) te sluipen. In de wereld van digitale communicatie zijn deze "spionnen" eigenlijk berichten die lichtelijk zijn vervormd door ruis. Meestal, als een bericht te ver afwijkt van het juiste patroon, zegt het beveiligingssysteem: "Nee, dat is geen geldig bericht," en gooit het het eruit.

Maar soms wordt het ingewikkeld. Stel je een scenario voor waarin één vervormd bericht verdacht dicht bij veel verschillende geldige spionnenpatronen tegelijkertijd ligt. In de wereld van de coderingstheorie wordt dit een list-decoding tegenvoorbeeld genoemd. Het is also als het vinden van een verdachte die op vijf verschillende mensen in de menigte lijkt. Als dit gebeurt, kan de standaard beveiligingscontrole in de war raken en zeggen: "Nou, misschien is het wel een van hen," terwijl dat niet zo is.

Dit artikel, geschreven door Yiwen Gao, Hong Yang, Yang Xu en Haibin Kan, pakt een specifieke, hoogwaardige versie van dit probleem aan. Ze kijken naar een beveiligingstest genaamd Mutual Correlated Agreement. Denk aan deze test als een manier om te controleren of een hele groep vervormde berichten, wanneer ze willekeurig worden gemengd (zoals het mixen van vijf smoothies tot één), nog steeds uitziet als een geldig spionnenpatroon.

De Grote Ontdekking: Het "Slechte Mengsel" Recept

De auteurs bewijzen een zeer specifieke, constructieve kwestie: Als je een list-decoding tegenvoorbeeld kunt vinden (een bericht dat op te veel geldige codes lijkt), dan kun je dat gebruiken om een nieuwe, iets andere code te bouwen die gegarandeerd faalt voor de "Mutual Correlated Agreement" test.

Hier is de magische truc die ze gebruiken, uitgelegd met een keukenanalogie:

De Opstelling: Je hebt een lijst van $L+1$ verschillende "geldige" recepten (codewoorden) die allemaal verrassend veel lijken op een vreemd, vervormd gerecht (het ontvangen woord).
De Uitbreiding: De auteurs nemen hun oorspronkelijke code en voegen één extra "ingrediënt" (een coördinaat) toe aan elk recept. Ze creëren twee speciale gerechten, $\pi_0$ $π_{0}$ en $\pi_1$ $π_{1}$ .
- $\pi_0$ is het oorspronkelijke vervormde gerecht, maar met een nul toegevoegd aan het einde.
- $\pi_1$ is een gerecht dat volledig uit nullen bestaat, behalve een enkele "1" aan het einde.
Het Mengen: Stel je nu voor dat je deze twee gerechten mengt met een geheim hoeveelheidje kruiden, $\alpha$ $α$ . Het nieuwe gerecht is $\pi_0 + \alpha \cdot \pi_1$ $π_{0} + α \cdot π_{1}$ .
- Op het oorspronkelijke deel van het gerecht ziet het er nog steeds uit als het vervormde woord.
- Aan het einde van het gerecht smaakt het precies naar de hoeveelheid kruiden $\alpha$ .
De Val: Omdat het oorspronkelijke vervormde woord dicht bij $L+1$ verschillende geldige recepten ligt, zijn er $L+1$ specifieke hoeveelheden kruiden ( $\alpha$ -waarden) die ervoor zorgen dat het gemengde gerecht er perfect uitziet als een van die geldige recepten (inclusief het nieuwe ingrediënt).
De Fout: Echter, de twee gerechten $\pi_0$ en $\pi_1$ zelf delen geen gemeenschappelijk patroon met de code op deze nieuwe, grotere set ingrediënten. Dit betekent dat het mengproces een "nep" overeenkomst heeft gecreëerd die er eigenlijk niet zou moeten zijn.

Het artikel bewijst dat als je $L+1$ nabijgelegen codewoorden hebt, je ten minste een bepaald aantal van deze "slechte kruidenhoeveelheden" (slechte combinatiepunten) kunt vinden. Specifiek is het aantal slechte punten ten minste:
$\left\lceil \frac{(L+1)q}{q+L} \right\rceil$
waarbij $q$ de grootte van het "smaakpalet" (het eindige veld) is.

De "Puncture and Append" Magische Truk

Er is een addertje onder het gras. Het toevoegen van dat extra ingrediënt maakte het gerecht groter (de code-lengte nam toe). Maar in de echte wereld kun je de grootte van het bericht niet zomaar veranderen; het moet dezelfde lengte behouden.

De auteurs voeren een slimme "Puncture and Append" manoeuvre uit:

Puncture (Puncteren): Ze nemen de oorspronkelijke code en verwijderen één ingrediënt (coördinaat) dat de structuur van de code niet breekt. Dit maakt de code iets kleiner.
Append (Toevoegen): Ze voegen het nieuwe "slechte" ingrediënt dat ze eerder vonden toe.
Resultaat: De code is weer terug op de oorspronkelijke grootte!

Het artikel laat zien dat deze nieuwe code, $C'$ , bijna identiek is aan de oude. Het verliest misschien een klein beetje aan "beveiligingsmarge" (de minimale afstand neemt met maximaal $1/n$ af), maar het is gegarandeerd dat het een hoge foutmarge heeft voor de Mutual Correlated Agreement test. In feite is de foutkans ten minste:
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$

De Vorm Behouden: Structureel Behoudende Codes

De auteurs stopten daar niet. Ze wisten dat codes in het echte leven vaak een speciale vorm hebben, zoals Reed-Solomon codes (gebruikt in CD's en QR-codes) of Algebraic-Geometry (AG) codes. Deze codes zijn niet zomaar willekeurige lijsten met getallen; ze zijn gebouwd met specifieke wiskundige afbeeldingen (zoals het evalueren van polynomen op specifieke punten).

Het artikel betoogt dat je niet zomaar elk willekeurig ingrediënt in deze speciale codes kunt gooien; het moet in het recept passen. De auteurs laten zien dat je de "Puncture and Append" truc nog steeds kunt uitvoeren terwijl de speciale structuur van de code intact blijft.

Voor Reed-Solomon codes vervang je gewoon één evaluatiepunt door een ander.
Voor AG-codes vervang je één "plaats" (een punt op een geometrische vorm) door een andere.

Ze bewijzen dat zelfs met deze strikte regels, als de oorspronkelijke code een list-decoding tegenvoorbeeld had, je een nieuwe code in dezelfde familie kunt bouwen die faalt voor de Mutual Correlated Agreement test met een gegarandeerde foutmarge.

Wat het Papier NIET Zegt

Het is belangrijk om te weten wat dit artikel niet doet:

Het zegt niet dat deze codes voor alle doeleinden kapot zijn. Het laat alleen zien dat als een specifieke "list-decoding tegenvoorbeeld" bestaat, een specifieke "Mutual Correlated Agreement" fout dan ook moet bestaan.
Het beweert niet het probleem op te lossen. In plaats daarvan construeert het een tegenvoorbeeld om aan te tonen dat de foutkans niet willekeurig klein gemaakt kan worden. Het is een "bewijs van onmogelijkheid" om de fout nul te maken in deze specifieke gevallen.
Het suggereert niet dat dit voor elke code gebeurt. Het is alleen van toepassing als je al een list-decoding tegenvoorbeeld kunt vinden (een bericht dat dicht bij $L+1$ codewoorden ligt).

Hoe Zeker Zijn Ze?

De auteurs zijn uiterst zelfverzekerd. Ze gokken niet en simuleren het niet op een computer. Ze leveren een constructief bewijs. Dit betekent dat ze niet alleen zeiden "het is mogelijk"; ze gaven een stapsgewijs recept (een algoritme) om de nieuwe code en de specifieke woorden te bouwen die het bestaan van de fout bewijzen.

Ze stellen expliciet dat, gegeven een ontvangen woord en $L+1$ nabijgelegen codewoorden, de constructie expliciet de nieuwe code en de getuige-woorden produceert. Dit is een hard wiskundig feit, geen suggestie.

De Kern voor de Nieuwsgierige Tiener

Beschouw dit artikel als een masterclass in "Hoe je een specifieke beveiligingstest kunt breken met een mazen in de wet."

De Maat in de Wet: Als een bericht dicht bij te veel geldige codes ( $L+1$ ) ligt, is het systeem al in de problemen.
De Breuk: De auteurs laten zien dat je die problemen kunt gebruiken om een "geldig" bericht te creëren door twee andere berichten te mengen.
Het Resultaat: Je kunt bewijzen dat de foutmarge voor deze mengtest ten minste $1/q$ keer een specifiek getal is dat $L$ en $q$ bevat.

Het artikel zegt in essentie: "Als je een list-decoding tegenvoorbeeld hebt, kun je niet beweren dat je code perfect veilig is voor deze mengaanvallen. Hier is exact hoe je de aanval bouwt en hoe groot de fout zal zijn."

Voor Reed-Solomon codes (de codes in je QR-codes) wordt de fout ondergrens:
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L(k-1)} \right\rceil$
waarbij $k$ de dimensie van de code is.

Het artikel concludeert dat de relatie tussen "list-decodability" en "mutual correlated agreement" nauw luistert: als de één faalt, moet de ander ook falen, en hier is de exacte wiskunde om dat te bewijzen.

Technisch Overzicht: List-Decoding Tegenvoorbeelden Leveren Ondergrenzen op voor Mutual Correlated Agreement Error

1. Probleemstelling

Het artikel behandelt de fundamentele vraag van Mutual Correlated Agreement (MCA) in de context van lineaire codes. MCA is een eigenschap die cruciaal is voor de betrouwbaarheid (soundness) van batched proximity testing, een mechanisme dat wordt gebruikt in succinct non-interactive arguments of knowledge (SNARKs) en Interactive Oracle Proofs of Proximity (IOPPs).

Specifiek onderzoekt MCA of een willekeurige lineaire combinatie van ontvangen woorden spuriaal een groot overeenkomstdomein kan creëren met een code die niet wordt verklaard door de gecorreleerde overeenkomststructuur van de oorspronkelijke woorden. Hoewel positieve resultaten (proximity gaps) bestaan voor diverse codefamilies tot bepaalde grenzen, is er een behoefte om de beperkingen te begrijpen: specifelijk hoe groot de foutkans (de waarschijnlijkheid van een "slecht" combinerend punt) kan zijn wanneer een code niet list-decodable is.

Het kernprobleem is het vestigen van een constructieve link tussen list-decoding tegenvoorbeelden (ontvangen woorden met meer dan $L$ codewoorden binnen een bepaalde afstand) en ondergrenzen op de MCA-fout. Eerdere werken hebben verbanden aangetoond tussen list-decodability en gecorreleerde overeenkomst, maar dit artikel beoogt een algemene, constructieve methode te bieden om expliciete ondergrenzen op de MCA-fout af te leiden uit list-decoding falen, waarbij de structurele eigenschappen van de codefamilie behouden blijven.

2. Methodologie

De auteurs hanteren een constructieve aanpak die gecentreerd is rond een "puncture-and-append" techniek. De methodologie verloopt in drie logische stadia:

Out-of-Domain Extensie:
Beginnend met een lineaire code $C$ die niet $(p, L)$ -list-decodable is, identificeren de auteurs een ontvangen woord $y$ en $L+1$ verschillende codewoorden $c_1, \dots, c_{L+1}$ binnen afstand $p$ . Ze construeren een uitgebreide code $C'$ van lengte $n+1$ door een nieuwe coördinaat toe te voegen.
- Twee woorden, $\pi_0$ en $\pi_1$ , worden gedefinieerd op het uitgebreide domein. $\pi_0$ draagt het oorspronkelijke ontvangen woord $y$ (met een toegevoegde nul), terwijl $\pi_1$ nul is op het oorspronkelijke domein en 1 op de nieuwe coördinaat.
- De auteurs maken gebruik van een lineair-algebraïsche collision bound (Lemma 1) om een vector $a$ te selecteren (die de toegevoegde kolom van de generator matrix definieert) zodanig dat de waarden $m_i \cdot a^T$ (waarbij $m_i$ de berichtvectoren van de nabijgelegen codewoorden zijn) een groot aantal verschillende waarden bevatten.
- Elke verschillende waarde komt overeen met een "slecht combinerend punt" $\alpha$ waar de lineaire combinatie $\pi_0 + \alpha \pi_1$ overeenkomt met een uitgebreid codewoord op een grote verzameling, terwijl het geen gecorreleerde overeenkomst bezit met het oorspronkelijke paar.
Puncture-and-Append (Lengtebehoud):
Om ervoor te zorgen dat de resulterende code dezelfde bloklengte $n$ heeft als de oorspronkelijke code, punchen (verwijderen) de auteurs één coördinaat uit de oorspronkelijke code voordat ze de nieuwe toevoegen.
- Ze bewijzen dat als de oorspronkelijke code niet $(p, L)$ -list-decodable is, er een coördinaat bestaat waarvan verwijdering de dimensie en de niet-list-decodability eigenschap behoudt (met een lichte aanpassing van de relatieve afstandsparameter).
- De "puncture one, append one"-procedure levert een code $C'$ op van lengte $n$ die de grote verzameling slechte combinerende punten behoudt die in de extensiestap zijn afgeleid.
Structuur-behoudende Generalisatie:
Om dit toe te passen op specifieke codefamilies (zoals Reed-Solomon of Algebraic-Geometry codes), generaliseren de auteurs de constructie naar geïndexeerde codefamilies.
- In plaats van een willekeurige vector voor de toegevoegde kolom te kiezen, selecteren ze een index uit een eindige verzameling $\Omega$ via een afbeelding $v: \Omega \to \mathbb{F}_q^k$ .
- Ze introduceren een collision bound $\lambda$ op de indexverzameling, wat garandeert dat verschillende berichten niet te frequent botsen op de beschikbare indices. Dit maakt het mogelijk dat de constructie binnen dezelfde codefamilie blijft (bijvoorbeeld door slechts één evaluatiepunt in een AG-code te wijzigen) terwijl de ondergrens op de MCA-fout behouden blijft.

3. Belangrijkste Bijdragen en Resultaten

Theorem 1 (Algemene Lineaire Codes):
Het artikel stelt vast dat als een lineaire code $C$ met dimensie $k$ en lengte $n$ niet $(p, L)$ -list-decodable is (met $p < \Delta(C) - 1/n$ ), er een gerelateerde code $C'$ bestaat van dezelfde lengte en dimensie waarvoor geldt:
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$
Bovendien voldoet de relatieve minimale afstand van $C'$ aan $\Delta(C') \geq \Delta(C) - 1/n$ . Als de minimale gewicht codewoorden van $C$ niet alle coördinaten dekken, kan de afstand exact behouden blijven ( $\Delta(C') \geq \Delta(C)$ ). De constructie is expliciet en produceert zowel de code $C'$ als een paar woorden die de fout getuigen.

Theorem 2 (Structuur-behoudende Versie):
Voor codefamilies geïndexeerd door een verzameling $\Omega$ met een kolomafbeelding $v$ , uitgaande van een collision bound $\lambda$ (waarbij elke niet-nul vector $u$ maximaal $\lambda$ indices $\omega$ heeft waarvoor $u \cdot v(\omega)^T = 0$ ), levert de constructie een code $C'$ binnen dezelfde familie op.

$C'$ verschilt van $C$ in maximaal één coördinaatindex.
De MCA-fout ondergrens wordt:
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)N}{N+L\lambda} \right\rceil$
waarbij $N = |\Omega|$ .

Corollaries voor Specifieke Codefamilies:

Algebraic-Geometry (AG) Codes: Door $\Omega$ te stellen als de verzameling rationale plaatsen en $\lambda = \deg(G)$ , tonen de auteurs aan dat als een AG-code niet list-decodable is, men een code kan verkrijgen met de gespecificeerde MCA-fout ondergrens door de evaluatie-divisor $D$ te wijzigen door maximaal één plaats te veranderen. De resulterende code blijft over dezelfde functieveld en Riemann-Roch ruimte.
Reed-Solomon (RS) Codes: Als een specialisatie waarbij $\Omega = \mathbb{F}_q$ en $\lambda = k-1$ (graad van polynomen), levert het resultaat een fout ondergrens van $\frac{1}{q} \lceil \frac{(L+1)q}{q+L(k-1)} \rceil$ . Dit bevestigt dat list-decoding falen in RS-codes direct significante MCA-fouten impliceren.

4. Betekenis en Claims

Het artikel claimt een constructieve en algemene methode te bieden voor het vertalen van list-decoding tegenvoorbeelden naar ondergrenzen op de mutual correlated agreement error.

Contrast met Voorgaand Werk: De auteurs merken op dat eerdere werken (bijv. Ben-Sasson et al., Crites en Stewart) vergelijkbare ondergrenzen voor Reed-Solomon codes afleidden met behulp van specifieke operaties zoals deling door $X-\beta$ , wat inherent de graad van de code verschuift (van $k$ naar $k+1$ ). In tegenstelling hiertoe behoudt de constructie van dit artikel de code-dimensie en de bloklengte, en is deze toepasbaar op willekeurige lineaire codes zonder dat er een graadverschuiving nodig is.
Structurele Integriteit: Een belangrijke bijdrage is het vermogen om de structurele familie van de code te behouden (bijvoorbeeld een AG-code als een AG-code over dezelfde ruimte houden) terwijl slechts één coördinaat wordt gewijzigd. Dit is cruciaief voor toepassingen waarbij de codefamilie wordt bepaald door de onderliggende algebraïsche structuur.
Implicaties voor Soundness: Door expliciet codes te construeren met een hoge MCA-fout vanuit list-decoding falen, kwantificeert het artikel de limieten van de betrouwbaarheid (soundness) in batched proximity testing. Het demonstreert dat als een code niet list-decodable is, men niet met hoge waarschijnlijkheid kan garanderen dat willekeurige lineaire combinaties ver van de code blijven; specifiek is de foutkans begrensd door de afgeleide formule.

Het werk stelt geen nieuwe experimentele protocollen of toekomstige toepassingen voor buiten het instantiëren van het principe voor AG en RS codes. De primaire bijdrage is theoretisch: het vestigen van een rigoureuze, constructieve brug tussen de eigenschappen van list-decoding en de mutual correlated agreement error bounds.