Computationally Efficient Codes for Adversarial Binary-Erasure Channels

Sijie Li, Prasad Krishnan, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and "sufficiently myopic"models. For the "insufficiently myopic"adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates.

שפה מקוריתאנגלית
כותר פרסום המארח2023 IEEE International Symposium on Information Theory, ISIT 2023
מוציא לאורInstitute of Electrical and Electronics Engineers Inc.
מספר עמודים6
מסת"ב (אלקטרוני)9781665475549
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2023
פורסם באופן חיצוניכן
אירוע2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, טייוואן
משך הזמן: 25 יוני 202330 יוני 2023

סדרות פרסומים

שםIEEE International Symposium on Information Theory - Proceedings
ISSN (מודפס)2157-8095


כנס2023 IEEE International Symposium on Information Theory, ISIT 2023

הערה ביבליוגרפית

Publisher Copyright:
© 2023 IEEE.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Computationally Efficient Codes for Adversarial Binary-Erasure Channels'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי