Överväga två parter som vill kommunicera för att utföra några interaktiva protokoll π. Men kommunikationskanalen mellan dem är bullrig: En motståndare ser allt som överförs över kanalen och kan ändra en konstant bråkdel av bitarna som han vill, vilket avbryter utförandet av π (som var avsedd för en felfri kanal). Om π bara innehåller ett enda långt meddelande skulle en bra felkorrigeringskod övervinna bullret med bara en konstant overhead i kommunikationen. Denna lösning är dock inte tillämplig på interaktiva protokoll som består av många korta meddelanden. Schulman (FOCS 92, STOC 93) presenterade begreppet interaktiv kodning: En simulator som, med tanke på alla protokoll π, kan simulera den (dvs. producera sin avsedda utskrift) även med konstant hastighet kontrariska kanalfel, och endast konstant (multiplikativ) kommunikation overhead. Fram till nyligen var dock körtiden för alla kända simulatorer exponentiell (eller subexponentiell) i kommunikationen komplexitet π (benämns N i detta arbete). Brakerski och Kalai (FOCS 12) presenterade nyligen en simulator som körs i tid poly (N ). Deras simulator är randomiserad (varje part vänder privata mynt) och har fel sannolikhet ungefär 2 −N. I detta arbete förbättrar vi den beräkningsmässiga komplexiteten i interaktiv kodning. Även om åtminstone N beräkningssteg krävs (även bara för att skriva ut utskriften av π), BK simulatorn körs i tid på (N 2 ). Vi presenterar två effektiva algoritmer för interaktiv kodning: Den första med beräkningskomplex O(N log N ) och exponentiellt liten (i N ) felsannolikhet; och den andra med beräkningskomplex O(N ), men felsannolikhet 1/poly(N ). (Sammanställningskomplexitet mäts i RAM-modellen.)
REF förbättrades när det gäller att beräkna komplexiteten i Brabrskis och Kalais konstruktion.
Fast Algorithms for Interactive Coding
{'venue': 'Electronic Colloquium on Computational Complexity', 'journal': 'Electronic Colloquium on Computational Complexity (ECCC)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}