Alice och Bob vill köra ett protokoll över en opålitlig kanal, där ett visst antal bitar vänds motsträvigt. Flera resultat tar ett protokoll som kräver L bitar av bullerfri kommunikation och gör det robust över en sådan kanal. I ett nyligen genombrott resultat, Haeupler beskrev en algoritm som skickar ett antal bitar som förmodas vara nära optimal i en sådan modell. Men, hans algoritm kräver kritiskt en förkunskaper om antalet bitar som kommer att vändas av motståndaren. Här beskriver vi en algoritm som inte kräver någon sådan kunskap. Om en motståndare vänder T bitar, vår algoritm skickar L + O (T + ε LT + L) log(LT + L) bits i förväntan och lyckas med hög sannolikhet i L. Det gör det utan någon föregående kunskap om T. Om man antar en förmodad lägre bunden av Haeupler, vårt resultat är optimal upp till logaritmiska faktorer. Vår algoritm bygger kritiskt på antagandet om en privat kanal. Vi visar att ett sådant antagande är nödvändigt när mängden buller är okänd. Våra resultat. Vårt huvudsakliga resultat sammanfattas i följande sats. Teorin 1. Algoritm 15 (Avsnitt 2) tolererar ett okänt antal kontradiktoriska fel, T, lyckas med hög sannolikhet i utskriftslängd 3, L, och om lyckas, skickar L + O (T + ε LT + L) log(LT + L) bitar i förväntan. Vi visar i Theorem 5 (Avsnitt B) att antalet bitar som skickas av vår algoritm ligger inom logaritmiska faktorer av optimal, antar en gissning från [12]. Som ytterligare resultat, visar vi ett samband mellan overhead uppstår när T = 0 och när T ≥ 1 för en mycket allmän klass av algoritmer, och härleda några nära-optimala resultat under denna klass (avsnitt B). Utmaningar. Kan vi anta tidigare resultat genom att gissa bullernivån i förväg? En underskattning hotar korrektheten om det faktiska antalet bitflips överstiger vad algoritmen kan tolerera. Omvänt leder en överskattning till att skicka fler bitar än nödvändigt. Därför behöver vi ett protokoll som anpassar sig till motståndarens handlingar. En idé är att anpassa antalet kommunikationsredundanser baserat på antalet upptäckta fel hittills. Detta innebär dock en ny utmaning eftersom parterna kan ha olika syn på antalet fel. De kommer att behöva synkronisera sina anpassningar över den bullriga kanalen. En annan teknisk utmaning är uppsägning, eftersom längden på det simulerade protokollet nödvändigtvis är okänd. Detta innebär att parterna sannolikt inte kommer att säga upp sig samtidigt. När en part har avslutat, är det en utmaning för den andra parten att upptäcka detta faktum baserat på bitar som mottagits över den bullriga kanalen. För att L-bitar ska överföras från Alice till Bob föreslår Shannon [20] en felkorrigeringskod för storlek O(L) som ger korrekt kommunikation över en bullrig kanal med sannolikhet 1 − e −  och (L). Vid första anblicken kan detta tyckas lösa vårt problem. Men överväga ett interaktivt protokoll med kommunikations komplexitet L, där Alice skickar en bit, sedan Bob skickar tillbaka en bit, och så vidare där värdet av varje del skickas beror på de tidigare bitar som mottagits. Två problem uppstår. För det första, att använda blockkodord är inte effektivt; för att uppnå en liten felsannolikhet, kan "dummy" bitar läggas till varje bit före kodning, men detta resulterar i en superlinjär uppblåsning i overhead. För det andra, på grund av interaktivitet, ett fel som uppstår i det förflutna kan förstöra alla beräkningar som kommer efter det. Således felkorrigering koder misslyckas när man hanterar interaktiva protokoll. Schulmans seminala arbete [18, 19] övervinner dessa hinder genom att beskriva en deterministisk metod för att simulera interaktiva protokoll på bullriga kanaler med endast en konstant faktor ökning av den totala kommunikations komplexiteten. Detta arbete har väckt ett starkt intresse för området (se [4] för en utmärkt undersökning). Schulmans system tolererar ett kontradiktoriskt buller på 1/240, och det är kritiskt beroende av begreppet trädkod för vilken en exponentiell tidsbyggnad ursprungligen tillhandahölls. Denna senare fastighet har motiverat arbetet med effektivare konstruktioner [5, 13, 17], och andra försök har fokuserat på användbara alternativa koder [9, 16]. Eleganta beräkningseffektiva system som kan tolerera en konstant negativ bullernivå har visats [1, 10]. Dessutom har ett stort antal kraftfulla resultat förbättrat den tolerabla stötdämpande bullernivån [2, 3, [6] [7] [8] 11 ]. 3 Specifikt med sannolikhet minst 1 −
Vi noterar att problemet i detta dokument kan ses som ett speciellt fall av interaktiv kommunikation i modellen från REF, där protokollet π bara skickar L bitar från Alice till Bob.
Interactive Communication with Unknown Noise Rate
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}