Vi inför en teknik för att etablera och förstärka klyftor mellan parametrar för nätkodning och indexkodningsproblem. Tekniken använder linjära program för att etablera separationer mellan kombinatoriska och kodningsteoretiska parametrar och tillämpar hypergraflexikografiska produkter för att förstärka dessa separationer. Detta innebär att kombinera de dubbla lösningarna av de lexikografiska multiplikatorerna och bevisa att detta är en giltig dubbel lösning av produkten. Vårt resultat är tillräckligt allmänt för att gälla för en stor familj av linjära program. Denna blandning av linjära program och lexikografiska produkter ger ett recept för att bygga hårda fall där gapet mellan kombinatoriska eller kodning-teoretiska parametrar är polynomiskt stort. Vi finner polynomiska luckor i fall där de största tidigare kända luckorna endast var små konstanta faktorer eller helt okända. Framför allt visar vi en polynomal separation mellan linjära och icke-linjära nätkodningshastigheter. Detta innebär att man utnyttjar en koppling mellan matriser och indexkodning för att fastställa en tidigare okänd separation mellan linjära och icke-linjära indexkodningshastigheter. Vi konstruerar också indexkodningsproblem med ett polynomgap mellan sändningsfrekvensen och den triviala lägre gränsen för vilken ingen lucka tidigare var känd. Tillhandahålla gränser för nätkodningsfrekvensen, men den värsta approximationsfaktorn för dessa gränser är fortfarande okänd. Det är t.ex. känt att det finns ett nät där icke-linjär nätkodning kan uppnå en hastighet som överskrider den bästa linjära nätkoden med en faktor på 11 10 [7], men det är inte känt om denna klyfta 1 kan förbättras till n 1−ε, eller ens möjligen till n. I detta dokument introducerar vi en allmän teknik för att förstärka många av dessa luckor genom att kombinera linjär programmering med hypergrafproduktverksamhet. Detta gör det till exempel möjligt för oss att bygga en familj av nätkodningsinstanser med n-meddelanden, där hastigheten för den bästa icke-linjära nätkoden överstiger hastigheten för den bästa (vektor-)linjära nätkoden med en faktor på minst n ε. En viktig ingrediens i vår teknik är indexkodning [5], [4], en klass av kommunikationsproblem där en server har en uppsättning meddelanden som den vill sända över en ljudlös kanal till en uppsättning mottagare. Varje mottagare är intresserad av ett av meddelandena och har sidinformation som innehåller någon delmängd av de andra meddelandena. Målet är att skapa ett optimalt kodningssystem (en som minimerar sändningslängden) som gör det möjligt för alla mottagare att hämta den information de behöver. Efter [3] använder vi β för att beteckna det begränsande värdet av informationshastigheten (dvs. förhållandet mellan sändningslängd och meddelandelängd) i detta optimala system, eftersom meddelandelängden tenderar till oändlighet. I vårt ramverk är indexkodning mest användbar för att isolera en underklass av nätkodningsproblem som kan kombineras med lexikografiska produkter. Men det är också ett viktigt och välstuderat problem i sig. Indexkodning är intimt relaterad till nätkodning i allmänhet. Den är i huvudsak likvärdig med det speciella fallet med nätkodning där endast en kant har ändlig kapacitet. 2 Dessutom [11] visar att linjär nätverkskodning kan vara 1 Litteraturen om nätverkskodning skiljer mellan linjära nätverkskoder, där meddelandena krävs för att vara delar av ett ändligt fält, och vektor-linjära nätverkskoder, där meddelandena är delar av ett finit-dimensionellt vektorutrymme över ett ändligt fält. Linjär kodning är svagare, och ett mellanrum i storlek n 1−ε är känt [10]. Vektor-linjär kodning är mycket kraftfullare, och inget gap större än 11/10 var känt innan vårt arbete. 2 Den unika ändliga kapacitet kant representerar sändningskanalen. Varje avsändare är ansluten till svansen av denna kant, varje mottagare är ansluten till sitt huvud, och varje mottagare har inkommande kanter direkt från en delmängd av avsändarna, som representerar sidoinformationen.
Blasiak m.fl. REF visade en klass av nätverk vars kapacitet är större än deras linjära kapacitet över något ändligt fält, med en faktor som växer polynomiskt med antalet meddelanden.
Lexicographic Products and the Power of Non-linear Network Coding
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}