Följande källkodning problem infördes av Birk och Kol: en avsändare innehar ett ord x 2 f0; 1g n, och önskar sända ett kodord till n mottagare, R1. ................................................................ Mottagaren R i är intresserad av x i, och har tidigare sidoinformation som innehåller någon delmängd av n bitar. Detta motsvarar en riktad graf G på n hörn, där ij är en kant iff R i vet bit x j. En indexkod för G är ett kodningsschema som gör det möjligt för varje R i att alltid rekonstruera x i, med tanke på hans sidoinformation. Den minsta ordlängden för en indexkod studerades av Bar-Yossef, Birk, Jayram och Kol (FOCS'06). De introducerade en grafparameter, minrk 2 (G), som helt karakteriserar längden av en optimal linjär indexkod för G. De visade att i olika fall linjära koder uppnå optimal ordlängd, och förmodade att linjär indexkodning är i själva verket alltid optimal. I detta arbete, vi motbevisa den viktigaste hypotesen av Bar-Yossef, Birk, Jayram, och Kol i följande starka betydelse: för alla > 0 och tillräckligt stor n, det finns en n-vertex graf G så att varje linjär indexkod för G kräver kodord av längd minst n 10, och ändå en icke-linjär indexkod för G har ett ordlängd av n. Detta uppnås genom en explicit konstruktion, som utökar Alons variant av den berömda Ramsey konstruktion av Frankl och Wilson. Dessutom studerar vi optimala indexkoder i olika, mindre begränsade naturliga modeller och bevisar flera relaterade egenskaper hos grafparametern minrk(G). Uri Stav tog doktorsexamen i datavetenskap från Tel-Aviv University, Tel-Aviv, Israel, 2008, under överinseende av professor Noga Alon. Hans huvudsakliga forskningsintressen är kombinatorik, grafteori, kodningsteori och teoretisk datavetenskap.
I REF visade dock Lubetzky och Stav att det finns vissa fall där ickelinjära index som kodar strikt överträffar linjär indexkodning.
Nonlinear Index Coding Outperforming the Linear Optimum
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}