---
_id: '14665'
abstract:
- lang: eng
  text: We derive lower bounds on the maximal rates for multiple packings in high-dimensional
    Euclidean spaces. For any N > 0 and L ∈ Z ≥2 , a multiple packing is a set C of
    points in R n such that any point in R n lies in the intersection of at most L
    - 1 balls of radius √ nN around points in C . This is a natural generalization
    of the sphere packing problem. We study the multiple packing problem for both
    bounded point sets whose points have norm at most √ nP for some constant P > 0,
    and unbounded point sets whose points are allowed to be anywhere in R n . Given
    a well-known connection with coding theory, multiple packings can be viewed as
    the Euclidean analog of list-decodable codes, which are well-studied over finite
    fields. We derive the best known lower bounds on the optimal multiple packing
    density. This is accomplished by establishing an inequality which relates the
    list-decoding error exponent for additive white Gaussian noise channels, a quantity
    of average-case nature, to the list-decoding radius, a quantity of worst-case
    nature. We also derive novel bounds on the list-decoding error exponent for infinite
    constellations and closed-form expressions for the list-decoding error exponents
    for the power-constrained AWGN channel, which may be of independent interest beyond
    multiple packing.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: 'Zhang Y, Vatedka S. Multiple packing: Lower bounds via error exponents. <i>IEEE
    Transactions on Information Theory</i>. 2023. doi:<a href="https://doi.org/10.1109/TIT.2023.3334032">10.1109/TIT.2023.3334032</a>'
  apa: 'Zhang, Y., &#38; Vatedka, S. (2023). Multiple packing: Lower bounds via error
    exponents. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href="https://doi.org/10.1109/TIT.2023.3334032">https://doi.org/10.1109/TIT.2023.3334032</a>'
  chicago: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via
    Error Exponents.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2023.
    <a href="https://doi.org/10.1109/TIT.2023.3334032">https://doi.org/10.1109/TIT.2023.3334032</a>.'
  ieee: 'Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via error exponents,”
    <i>IEEE Transactions on Information Theory</i>. IEEE, 2023.'
  ista: 'Zhang Y, Vatedka S. 2023. Multiple packing: Lower bounds via error exponents.
    IEEE Transactions on Information Theory.'
  mla: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Error
    Exponents.” <i>IEEE Transactions on Information Theory</i>, IEEE, 2023, doi:<a
    href="https://doi.org/10.1109/TIT.2023.3334032">10.1109/TIT.2023.3334032</a>.'
  short: Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory (2023).
date_created: 2023-12-10T23:01:00Z
date_published: 2023-11-16T00:00:00Z
date_updated: 2023-12-18T07:46:45Z
day: '16'
department:
- _id: MaMo
doi: 10.1109/TIT.2023.3334032
external_id:
  arxiv:
  - '2211.04408'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2211.04408
month: '11'
oa: 1
oa_version: Preprint
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: epub_ahead
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Multiple packing: Lower bounds via error exponents'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14751'
abstract:
- lang: eng
  text: 'We consider zero-error communication over a two-transmitter deterministic
    adversarial multiple access channel (MAC) governed by an adversary who has access
    to the transmissions of both senders (hence called omniscient ) and aims to maliciously
    corrupt the communication. None of the encoders, jammer and decoder is allowed
    to randomize using private or public randomness. This enforces a combinatorial
    nature of the problem. Our model covers a large family of channels studied in
    the literature, including all deterministic discrete memoryless noisy or noiseless
    MACs. In this work, given an arbitrary two-transmitter deterministic omniscient
    adversarial MAC, we characterize when the capacity region: 1) has nonempty interior
    (in particular, is two-dimensional); 2) consists of two line segments (in particular,
    has empty interior); 3) consists of one line segment (in particular, is one-dimensional);
    4) or only contains (0,0) (in particular, is zero-dimensional). This extends a
    recent result by Wang et al. (201 9) from the point-to-point setting to the multiple
    access setting. Indeed, our converse arguments build upon their generalized Plotkin
    bound and involve delicate case analysis. One of the technical challenges is to
    take care of both “joint confusability” and “marginal confusability”. In particular,
    the treatment of marginal confusability does not follow from the point-to-point
    results by Wang et al. Our achievability results follow from random coding with
    expurgation.'
acknowledgement: "The author would like to thank Amitalok J. Budkuley and Sidharth
  Jaggi for many helpful discussions at the early stage of this work. He would also
  like to thank Nir Ailon, Qi Cao, and Chandra Nair for discussions on a related problem
  regarding zero-error binary adder MACs.\r\nThe work of Yihan Zhang was supported
  by the European Union’s Horizon 2020 Research and Innovation Programme under Grant
  682203-ERC-[Inf-Speed-Tradeoff]"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
citation:
  ama: Zhang Y. Zero-error communication over adversarial MACs. <i>IEEE Transactions
    on Information Theory</i>. 2023;69(7):4093-4127. doi:<a href="https://doi.org/10.1109/tit.2023.3257239">10.1109/tit.2023.3257239</a>
  apa: Zhang, Y. (2023). Zero-error communication over adversarial MACs. <i>IEEE Transactions
    on Information Theory</i>. Institute of Electrical and Electronics Engineers.
    <a href="https://doi.org/10.1109/tit.2023.3257239">https://doi.org/10.1109/tit.2023.3257239</a>
  chicago: Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” <i>IEEE
    Transactions on Information Theory</i>. Institute of Electrical and Electronics
    Engineers, 2023. <a href="https://doi.org/10.1109/tit.2023.3257239">https://doi.org/10.1109/tit.2023.3257239</a>.
  ieee: Y. Zhang, “Zero-error communication over adversarial MACs,” <i>IEEE Transactions
    on Information Theory</i>, vol. 69, no. 7. Institute of Electrical and Electronics
    Engineers, pp. 4093–4127, 2023.
  ista: Zhang Y. 2023. Zero-error communication over adversarial MACs. IEEE Transactions
    on Information Theory. 69(7), 4093–4127.
  mla: Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” <i>IEEE Transactions
    on Information Theory</i>, vol. 69, no. 7, Institute of Electrical and Electronics
    Engineers, 2023, pp. 4093–127, doi:<a href="https://doi.org/10.1109/tit.2023.3257239">10.1109/tit.2023.3257239</a>.
  short: Y. Zhang, IEEE Transactions on Information Theory 69 (2023) 4093–4127.
date_created: 2024-01-08T13:04:54Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2024-01-09T08:45:24Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/tit.2023.3257239
external_id:
  arxiv:
  - '2101.12426'
intvolume: '        69'
issue: '7'
keyword:
- Computer Science Applications
- Information Systems
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2101.12426
month: '07'
oa: 1
oa_version: Preprint
page: 4093-4127
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zero-error communication over adversarial MACs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2023'
...
---
_id: '13269'
abstract:
- lang: eng
  text: This paper is a collection of results on combinatorial properties of codes
    for the Z-channel . A Z-channel with error fraction τ takes as input a length-
    n binary codeword and injects in an adversarial manner up to n τ asymmetric errors,
    i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that
    the largest ( L - 1)-list-decodable code for the Z-channel with error fraction
    τ has exponential size (in n ) if τ is less than a critical value that we call
    the ( L - 1)- list-decoding Plotkin point and has constant size if τ is larger
    than the threshold. The ( L -1)-list-decoding Plotkin point is known to be L -1/L-1
    – L -L/ L-1 , which equals 1/4 for unique-decoding with L -1 = 1. In this paper,
    we derive various results for the size of the largest codes above and below the
    list-decoding Plotkin point. In particular, we show that the largest ( L -1)-list-decodable
    code ε-above the Plotkin point, for any given sufficiently small positive constant
    ε > 0, has size Θ L (ε -3/2 ) for any L - 1 ≥ 1. We also devise upper and lower
    bounds on the exponential size of codes below the list-decoding Plotkin point.
acknowledgement: "Nikita Polyanskii’s research was conducted in part during October
  2020 - December 2021 with the Technical University of Munich and the Skolkovo Institute
  of Science and Technology. His work was supported by the German Research Foundation
  (Deutsche Forschungsgemeinschaft, DFG) under Grant No. WA3907/1-1 and the Russian
  Foundation for Basic Research (RFBR)\r\nunder Grant No. 20-01-00559.\r\nYihan Zhang
  is supported by funding from the European Union’s Horizon 2020 research and innovation
  programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nikita
  full_name: Polyanskii, Nikita
  last_name: Polyanskii
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
citation:
  ama: Polyanskii N, Zhang Y. Codes for the Z-channel. <i>IEEE Transactions on Information
    Theory</i>. 2023;69(10):6340-6357. doi:<a href="https://doi.org/10.1109/TIT.2023.3292219">10.1109/TIT.2023.3292219</a>
  apa: Polyanskii, N., &#38; Zhang, Y. (2023). Codes for the Z-channel. <i>IEEE Transactions
    on Information Theory</i>. Institute of Electrical and Electronics Engineers.
    <a href="https://doi.org/10.1109/TIT.2023.3292219">https://doi.org/10.1109/TIT.2023.3292219</a>
  chicago: Polyanskii, Nikita, and Yihan Zhang. “Codes for the Z-Channel.” <i>IEEE
    Transactions on Information Theory</i>. Institute of Electrical and Electronics
    Engineers, 2023. <a href="https://doi.org/10.1109/TIT.2023.3292219">https://doi.org/10.1109/TIT.2023.3292219</a>.
  ieee: N. Polyanskii and Y. Zhang, “Codes for the Z-channel,” <i>IEEE Transactions
    on Information Theory</i>, vol. 69, no. 10. Institute of Electrical and Electronics
    Engineers, pp. 6340–6357, 2023.
  ista: Polyanskii N, Zhang Y. 2023. Codes for the Z-channel. IEEE Transactions on
    Information Theory. 69(10), 6340–6357.
  mla: Polyanskii, Nikita, and Yihan Zhang. “Codes for the Z-Channel.” <i>IEEE Transactions
    on Information Theory</i>, vol. 69, no. 10, Institute of Electrical and Electronics
    Engineers, 2023, pp. 6340–57, doi:<a href="https://doi.org/10.1109/TIT.2023.3292219">10.1109/TIT.2023.3292219</a>.
  short: N. Polyanskii, Y. Zhang, IEEE Transactions on Information Theory 69 (2023)
    6340–6357.
date_created: 2023-07-23T22:01:14Z
date_published: 2023-07-04T00:00:00Z
date_updated: 2024-01-29T11:10:54Z
day: '04'
department:
- _id: MaMo
doi: 10.1109/TIT.2023.3292219
external_id:
  arxiv:
  - '2105.01427'
  isi:
  - '001069680100011'
intvolume: '        69'
isi: 1
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2105.01427
month: '07'
oa: 1
oa_version: Preprint
page: 6340-6357
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Codes for the Z-channel
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2023'
...
---
_id: '14083'
abstract:
- lang: eng
  text: "In this work we consider the list-decodability and list-recoverability of
    arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable
    if every radius pn Hamming ball contains less than L codewords; (p,\U0001D4C1,L)_q-list-recoverability
    is a generalization where we place radius pn Hamming balls on every point of a
    combinatorial rectangle with side length \U0001D4C1 and again stipulate that there
    be less than L codewords.\r\nOur main contribution is to precisely calculate the
    maximum value of p for which there exist infinite families of positive rate (p,\U0001D4C1,L)_q-list-recoverable
    codes, the quantity we call the zero-rate threshold. Denoting this value by p_*,
    we in fact show that codes correcting a p_*+ε fraction of errors must have size
    O_ε(1), i.e., independent of n. Such a result is typically referred to as a \"Plotkin
    bound.\" To complement this, a standard random code with expurgation construction
    shows that there exist positive rate codes correcting a p_*-ε fraction of errors.
    We also follow a classical proof template (typically attributed to Elias and Bassalygo)
    to derive from the zero-rate threshold other tradeoffs between rate and decoding
    radius for list-decoding and list-recovery.\r\nTechnically, proving the Plotkin
    bound boils down to demonstrating the Schur convexity of a certain function defined
    on the q-simplex as well as the convexity of a univariate function derived from
    it. We remark that an earlier argument claimed similar results for q-ary list-decoding;
    however, we point out that this earlier proof is flawed."
acknowledgement: "Nicolas Resch: Research supported in part by ERC H2020 grant No.74079
  (ALGSTRONGCRYPTO). Chen Yuan: Research supported in part by the National Key Research
  and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the
  National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.\r\nAcknowledgements
  YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions."
alternative_title:
- LIPIcs
article_number: '99'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Nicolas
  full_name: Resch, Nicolas
  last_name: Resch
- first_name: Chen
  full_name: Yuan, Chen
  last_name: Yuan
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
citation:
  ama: 'Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for
    list-decoding and list-recovery. In: <i>50th International Colloquium on Automata,
    Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">10.4230/LIPIcs.ICALP.2023.99</a>'
  apa: 'Resch, N., Yuan, C., &#38; Zhang, Y. (2023). Zero-rate thresholds and new
    capacity bounds for list-decoding and list-recovery. In <i>50th International
    Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn,
    Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>'
  chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New
    Capacity Bounds for List-Decoding and List-Recovery.” In <i>50th International
    Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>.
  ieee: N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds
    for list-decoding and list-recovery,” in <i>50th International Colloquium on Automata,
    Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.
  ista: 'Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds
    for list-decoding and list-recovery. 50th International Colloquium on Automata,
    Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
    and Programming, LIPIcs, vol. 261, 99.'
  mla: Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding
    and List-Recovery.” <i>50th International Colloquium on Automata, Languages, and
    Programming</i>, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023, doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">10.4230/LIPIcs.ICALP.2023.99</a>.
  short: N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata,
    Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023.
conference:
  end_date: 2023-07-14
  location: Paderborn, Germany
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2023-07-10
date_created: 2023-08-20T22:01:13Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:26:01Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ICALP.2023.99
external_id:
  arxiv:
  - '2210.07754'
file:
- access_level: open_access
  checksum: a449143fec3fbebb092cb8ef3b53c226
  content_type: application/pdf
  creator: dernst
  date_created: 2023-08-21T07:23:18Z
  date_updated: 2023-08-21T07:23:18Z
  file_id: '14091'
  file_name: 2023_LIPIcsICALP_Resch.pdf
  file_size: 1141497
  relation: main_file
  success: 1
file_date_updated: 2023-08-21T07:23:18Z
has_accepted_license: '1'
intvolume: '       261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783959772785'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '12838'
abstract:
- lang: eng
  text: We study the problem of high-dimensional multiple packing in Euclidean space.
    Multiple packing is a natural generalization of sphere packing and is defined
    as follows. Let N > 0 and L ∈ Z ≽2 . A multiple packing is a set C of points in
    R n such that any point in R n lies in the intersection of at most L – 1 balls
    of radius √ nN around points in C . Given a well-known connection with coding
    theory, multiple packings can be viewed as the Euclidean analog of list-decodable
    codes, which are well-studied for finite fields. In this paper, we derive the
    best known lower bounds on the optimal density of list-decodable infinite constellations
    for constant L under a stronger notion called average-radius multiple packing.
    To this end, we apply tools from high-dimensional geometry and large deviation
    theory.
acknowledgement: "YZ thanks Jiajin Li for making the observation given by Equation
  (23). He also would like to thank Nir Ailon and Ely Porat for several helpful conversations
  throughout this project, and Alexander Barg for insightful comments on the manuscript.\r\nYZ
  has received funding from the European Union’s Horizon 2020 research and innovation
  programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]. The work of
  SV was supported by a seed grant from IIT Hyderabad and the start-up research grant
  from the Science and Engineering Research Board, India (SRG/2020/000910)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: 'Zhang Y, Vatedka S. Multiple packing: Lower bounds via infinite constellations.
    <i>IEEE Transactions on Information Theory</i>. 2023;69(7):4513-4527. doi:<a href="https://doi.org/10.1109/TIT.2023.3260950">10.1109/TIT.2023.3260950</a>'
  apa: 'Zhang, Y., &#38; Vatedka, S. (2023). Multiple packing: Lower bounds via infinite
    constellations. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href="https://doi.org/10.1109/TIT.2023.3260950">https://doi.org/10.1109/TIT.2023.3260950</a>'
  chicago: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via
    Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>. IEEE,
    2023. <a href="https://doi.org/10.1109/TIT.2023.3260950">https://doi.org/10.1109/TIT.2023.3260950</a>.'
  ieee: 'Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via infinite constellations,”
    <i>IEEE Transactions on Information Theory</i>, vol. 69, no. 7. IEEE, pp. 4513–4527,
    2023.'
  ista: 'Zhang Y, Vatedka S. 2023. Multiple packing: Lower bounds via infinite constellations.
    IEEE Transactions on Information Theory. 69(7), 4513–4527.'
  mla: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Infinite
    Constellations.” <i>IEEE Transactions on Information Theory</i>, vol. 69, no.
    7, IEEE, 2023, pp. 4513–27, doi:<a href="https://doi.org/10.1109/TIT.2023.3260950">10.1109/TIT.2023.3260950</a>.'
  short: Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 69 (2023) 4513–4527.
date_created: 2023-04-16T22:01:09Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-12-13T11:16:46Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TIT.2023.3260950
external_id:
  arxiv:
  - '2211.04407'
  isi:
  - '001017307000023'
intvolume: '        69'
isi: 1
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2211.04407
month: '07'
oa: 1
oa_version: Preprint
page: 4513-4527
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Multiple packing: Lower bounds via infinite constellations'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2023'
...
---
_id: '11639'
abstract:
- lang: eng
  text: We study the list decodability of different ensembles of codes over the real
    alphabet under the assumption of an omniscient adversary. It is a well-known result
    that when the source and the adversary have power constraints P and N respectively,
    the list decoding capacity is equal to 1/2logP/N. Random spherical codes achieve
    constant list sizes, and the goal of the present paper is to obtain a better understanding
    of the smallest achievable list size as a function of the gap to capacity. We
    show a reduction from arbitrary codes to spherical codes, and derive a lower bound
    on the list size of typical random spherical codes. We also give an upper bound
    on the list size achievable using nested Construction-A lattices and infinite
    Construction-A lattices. We then define and study a class of infinite constellations
    that generalize Construction-A lattices and prove upper and lower bounds for the
    same. Other goodness properties such as packing goodness and AWGN goodness of
    infinite constellations are proved along the way. Finally, we consider random
    lattices sampled from the Haar distribution and show that if a certain conjecture
    that originates in analytic number theory is true, then the list size grows as
    a polynomial function of the gap-to-capacity.
acknowledgement: "This work was done when Shashank Vatedka was at the Chinese University
  of Hong Kong, where he was supported in part by CUHK Direct Grants 4055039 and 4055077.
  He would like to acknowledge funding from a seed grant offered by IIT Hyderabad
  and the Start-up Research Grant (SRG/2020/000910) from the Science and Engineering
  Board, India. Yihan Zhang has received funding from the European Union’s Horizon
  2020 research and innovation programme\r\nunder grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: Zhang Y, Vatedka S. List decoding random Euclidean codes and Infinite constellations.
    <i>IEEE Transactions on Information Theory</i>. 2022;68(12):7753-7786. doi:<a
    href="https://doi.org/10.1109/TIT.2022.3189542">10.1109/TIT.2022.3189542</a>
  apa: Zhang, Y., &#38; Vatedka, S. (2022). List decoding random Euclidean codes and
    Infinite constellations. <i>IEEE Transactions on Information Theory</i>. IEEE.
    <a href="https://doi.org/10.1109/TIT.2022.3189542">https://doi.org/10.1109/TIT.2022.3189542</a>
  chicago: Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes
    and Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>.
    IEEE, 2022. <a href="https://doi.org/10.1109/TIT.2022.3189542">https://doi.org/10.1109/TIT.2022.3189542</a>.
  ieee: Y. Zhang and S. Vatedka, “List decoding random Euclidean codes and Infinite
    constellations,” <i>IEEE Transactions on Information Theory</i>, vol. 68, no.
    12. IEEE, pp. 7753–7786, 2022.
  ista: Zhang Y, Vatedka S. 2022. List decoding random Euclidean codes and Infinite
    constellations. IEEE Transactions on Information Theory. 68(12), 7753–7786.
  mla: Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes and
    Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>, vol.
    68, no. 12, IEEE, 2022, pp. 7753–86, doi:<a href="https://doi.org/10.1109/TIT.2022.3189542">10.1109/TIT.2022.3189542</a>.
  short: Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 68 (2022) 7753–7786.
date_created: 2022-07-24T22:01:42Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-03T12:12:19Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TIT.2022.3189542
external_id:
  arxiv:
  - '1901.03790'
  isi:
  - '000891796100007'
intvolume: '        68'
isi: 1
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1901.03790
month: '12'
oa: 1
oa_version: Preprint
page: 7753-7786
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: List decoding random Euclidean codes and Infinite constellations
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '12011'
abstract:
- lang: eng
  text: We characterize the capacity for the discrete-time arbitrarily varying channel
    with discrete inputs, outputs, and states when (a) the encoder and decoder do
    not share common randomness, (b) the input and state are subject to cost constraints,
    (c) the transition matrix of the channel is deterministic given the state, and
    (d) at each time step the adversary can only observe the current and past channel
    inputs when choosing the state at that time. The achievable strategy involves
    stochastic encoding together with list decoding and a disambiguation step. The
    converse uses a two-phase "babble-and-push" strategy where the adversary chooses
    the state randomly in the first phase, list decodes the output, and then chooses
    state inputs to symmetrize the channel in the second phase. These results generalize
    prior work on specific channels models (additive, erasure) to general discrete
    alphabets and models.
acknowledgement: The work of ADS and ML was supported in part by the US National Science
  Foundation under awards CCF-1909468 and CCF-1909451.
article_processing_charge: No
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Sidharth
  full_name: Jaggi, Sidharth
  last_name: Jaggi
- first_name: Michael
  full_name: Langberg, Michael
  last_name: Langberg
- first_name: Anand D.
  full_name: Sarwate, Anand D.
  last_name: Sarwate
citation:
  ama: 'Zhang Y, Jaggi S, Langberg M, Sarwate AD. The capacity of causal adversarial
    channels. In: <i>2022 IEEE International Symposium on Information Theory</i>.
    Vol 2022. IEEE; 2022:2523-2528. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834709">10.1109/ISIT50566.2022.9834709</a>'
  apa: 'Zhang, Y., Jaggi, S., Langberg, M., &#38; Sarwate, A. D. (2022). The capacity
    of causal adversarial channels. In <i>2022 IEEE International Symposium on Information
    Theory</i> (Vol. 2022, pp. 2523–2528). Espoo, Finland: IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834709">https://doi.org/10.1109/ISIT50566.2022.9834709</a>'
  chicago: Zhang, Yihan, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. “The
    Capacity of Causal Adversarial Channels.” In <i>2022 IEEE International Symposium
    on Information Theory</i>, 2022:2523–28. IEEE, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834709">https://doi.org/10.1109/ISIT50566.2022.9834709</a>.
  ieee: Y. Zhang, S. Jaggi, M. Langberg, and A. D. Sarwate, “The capacity of causal
    adversarial channels,” in <i>2022 IEEE International Symposium on Information
    Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2523–2528.
  ista: 'Zhang Y, Jaggi S, Langberg M, Sarwate AD. 2022. The capacity of causal adversarial
    channels. 2022 IEEE International Symposium on Information Theory. ISIT: Internation
    Symposium on Information Theory vol. 2022, 2523–2528.'
  mla: Zhang, Yihan, et al. “The Capacity of Causal Adversarial Channels.” <i>2022
    IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022,
    pp. 2523–28, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834709">10.1109/ISIT50566.2022.9834709</a>.
  short: Y. Zhang, S. Jaggi, M. Langberg, A.D. Sarwate, in:, 2022 IEEE International
    Symposium on Information Theory, IEEE, 2022, pp. 2523–2528.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:03Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2022-09-05T09:09:15Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834709
external_id:
  arxiv:
  - '2205.06708'
intvolume: '      2022'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2205.06708'
month: '08'
oa: 1
oa_version: Preprint
page: 2523-2528
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: The capacity of causal adversarial channels
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12013'
abstract:
- lang: eng
  text: We consider the problem of communication over adversarial channels with feedback.
    Two parties comprising sender Alice and receiver Bob seek to communicate reliably.
    An adversary James observes Alice's channel transmission entirely and chooses,
    maliciously, its additive channel input or jamming state thereby corrupting Bob's
    observation. Bob can communicate over a one-way reverse link with Alice; we assume
    that transmissions over this feedback link cannot be corrupted by James. Our goal
    in this work is to study the optimum throughput or capacity over such channels
    with feedback. We first present results for the quadratically-constrained additive
    channel where communication is known to be impossible when the noise-to-signal
    (power) ratio (NSR) is at least 1. We present a novel achievability scheme to
    establish that positive rate communication is possible even when the NSR is as
    high as 8/9. We also present new converse upper bounds on the capacity of this
    channel under potentially stochastic encoders and decoders. We also study feedback
    communication over the more widely studied q-ary alphabet channel under additive
    noise. For the q -ary channel, where q > 2, it is well known that capacity is
    positive under full feedback if and only if the adversary can corrupt strictly
    less than half the transmitted symbols. We generalize this result and show that
    the same threshold holds for positive rate communication when the noiseless feedback
    may only be partial; our scheme employs a stochastic decoder. We extend this characterization,
    albeit partially, to fully deterministic schemes under partial noiseless feedback.
    We also present new converse upper bounds for q-ary channels under full feedback,
    where the encoder and/or decoder may privately randomize. Our converse results
    bring to the fore an interesting alternate expression for the well known converse
    bound for the q—ary channel under full feedback which, when specialized to the
    binary channel, also equals its known capacity.
article_processing_charge: No
author:
- first_name: Pranav
  full_name: Joshi, Pranav
  last_name: Joshi
- first_name: Amritakshya
  full_name: Purkayastha, Amritakshya
  last_name: Purkayastha
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Amitalok J.
  full_name: Budkuley, Amitalok J.
  last_name: Budkuley
- first_name: Sidharth
  full_name: Jaggi, Sidharth
  last_name: Jaggi
citation:
  ama: 'Joshi P, Purkayastha A, Zhang Y, Budkuley AJ, Jaggi S. On the capacity of
    additive AVCs with feedback. In: <i>2022 IEEE International Symposium on Information
    Theory</i>. Vol 2022. IEEE; 2022:504-509. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834850">10.1109/ISIT50566.2022.9834850</a>'
  apa: 'Joshi, P., Purkayastha, A., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S. (2022).
    On the capacity of additive AVCs with feedback. In <i>2022 IEEE International
    Symposium on Information Theory</i> (Vol. 2022, pp. 504–509). Espoo, Finland:
    IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834850">https://doi.org/10.1109/ISIT50566.2022.9834850</a>'
  chicago: Joshi, Pranav, Amritakshya Purkayastha, Yihan Zhang, Amitalok J. Budkuley,
    and Sidharth Jaggi. “On the Capacity of Additive AVCs with Feedback.” In <i>2022
    IEEE International Symposium on Information Theory</i>, 2022:504–9. IEEE, 2022.
    <a href="https://doi.org/10.1109/ISIT50566.2022.9834850">https://doi.org/10.1109/ISIT50566.2022.9834850</a>.
  ieee: P. Joshi, A. Purkayastha, Y. Zhang, A. J. Budkuley, and S. Jaggi, “On the
    capacity of additive AVCs with feedback,” in <i>2022 IEEE International Symposium
    on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 504–509.
  ista: 'Joshi P, Purkayastha A, Zhang Y, Budkuley AJ, Jaggi S. 2022. On the capacity
    of additive AVCs with feedback. 2022 IEEE International Symposium on Information
    Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 504–509.'
  mla: Joshi, Pranav, et al. “On the Capacity of Additive AVCs with Feedback.” <i>2022
    IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022,
    pp. 504–09, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834850">10.1109/ISIT50566.2022.9834850</a>.
  short: P. Joshi, A. Purkayastha, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022 IEEE
    International Symposium on Information Theory, IEEE, 2022, pp. 504–509.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:04Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2022-09-05T10:23:35Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834850
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 504-509
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the capacity of additive AVCs with feedback
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12014'
abstract:
- lang: eng
  text: We study the problem of high-dimensional multiple packing in Euclidean space.
    Multiple packing is a natural generalization of sphere packing and is defined
    as follows. Let N > 0 and L∈Z≥2. A multiple packing is a set C of points in Rn
    such that any point in Rn lies in the intersection of at most L – 1 balls of radius
    nN−−−√ around points in C. Given a well-known connection with coding theory, multiple
    packings can be viewed as the Euclidean analog of list-decodable codes, which
    are well-studied for finite fields. In this paper, we exactly pin down the asymptotic
    density of (expurgated) Poisson Point Processes under a stronger notion called
    average-radius multiple packing. To this end, we apply tools from high-dimensional
    geometry and large deviation theory. This gives rise to the best known lower bound
    on the largest multiple packing density. Our result corrects a mistake in a previous
    paper by Blinovsky [Bli05].
article_processing_charge: No
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: 'Zhang Y, Vatedka S. List-decodability of Poisson Point Processes. In: <i>2022
    IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2559-2564.
    doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834512">10.1109/ISIT50566.2022.9834512</a>'
  apa: 'Zhang, Y., &#38; Vatedka, S. (2022). List-decodability of Poisson Point Processes.
    In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022,
    pp. 2559–2564). Espoo, Finland: IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834512">https://doi.org/10.1109/ISIT50566.2022.9834512</a>'
  chicago: Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point
    Processes.” In <i>2022 IEEE International Symposium on Information Theory</i>,
    2022:2559–64. IEEE, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834512">https://doi.org/10.1109/ISIT50566.2022.9834512</a>.
  ieee: Y. Zhang and S. Vatedka, “List-decodability of Poisson Point Processes,” in
    <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland,
    2022, vol. 2022, pp. 2559–2564.
  ista: 'Zhang Y, Vatedka S. 2022. List-decodability of Poisson Point Processes. 2022
    IEEE International Symposium on Information Theory. ISIT: Internation Symposium
    on Information Theory vol. 2022, 2559–2564.'
  mla: Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.”
    <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE,
    2022, pp. 2559–64, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834512">10.1109/ISIT50566.2022.9834512</a>.
  short: Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information
    Theory, IEEE, 2022, pp. 2559–2564.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:04Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2022-09-05T09:23:04Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834512
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 2559-2564
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: List-decodability of Poisson Point Processes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12015'
abstract:
- lang: eng
  text: We study the problem of high-dimensional multiple packing in Euclidean space.
    Multiple packing is a natural generalization of sphere packing and is defined
    as follows. Let P, N > 0 and L∈Z≥2. A multiple packing is a set C of points in
    Bn(0–,nP−−−√) such that any point in ℝ n lies in the intersection of at most L
    – 1 balls of radius nN−−−√ around points in C. 1 In this paper, we derive two
    lower bounds on the largest possible density of a multiple packing. These bounds
    are obtained through a stronger notion called average-radius multiple packing.
    Specifically, we exactly pin down the asymptotics of (expurgated) Gaussian codes
    and (expurgated) spherical codes under average-radius multiple packing. To this
    end, we apply tools from high-dimensional geometry and large deviation theory.
    The bound for spherical codes matches the previous best known bound which was
    obtained for the standard (weaker) notion of multiple packing through a curious
    connection with error exponents [Bli99], [ZV21]. The bound for Gaussian codes
    suggests that they are strictly inferior to spherical codes.
article_processing_charge: No
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: 'Zhang Y, Vatedka S. Lower bounds for multiple packing. In: <i>2022 IEEE International
    Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:3085-3090. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834443">10.1109/ISIT50566.2022.9834443</a>'
  apa: 'Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds for multiple packing. In
    <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp.
    3085–3090). Espoo, Finland: IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834443">https://doi.org/10.1109/ISIT50566.2022.9834443</a>'
  chicago: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.”
    In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:3085–90.
    IEEE, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834443">https://doi.org/10.1109/ISIT50566.2022.9834443</a>.
  ieee: Y. Zhang and S. Vatedka, “Lower bounds for multiple packing,” in <i>2022 IEEE
    International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol.
    2022, pp. 3085–3090.
  ista: 'Zhang Y, Vatedka S. 2022. Lower bounds for multiple packing. 2022 IEEE International
    Symposium on Information Theory. ISIT: Internation Symposium on Information Theory
    vol. 2022, 3085–3090.'
  mla: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” <i>2022
    IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022,
    pp. 3085–90, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834443">10.1109/ISIT50566.2022.9834443</a>.
  short: Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information
    Theory, IEEE, 2022, pp. 3085–3090.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:05Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2022-09-05T10:39:04Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834443
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 3085-3090
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for multiple packing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12017'
abstract:
- lang: eng
  text: 'In the classic adversarial communication problem, two parties communicate
    over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily
    varying channels (AVCs) offer an elegant framework to study a wide range of interesting
    adversary models. The optimal throughput or capacity over such AVCs is intimately
    tied to the underlying adversary model; in some cases, capacity is unknown and
    the problem is known to be notoriously hard. The omniscient adversary, one which
    knows the sender’s entire channel transmission a priori, is one of such classic
    models of interest; the capacity under such an adversary remains an exciting open
    problem. The myopic adversary is a generalization of that model where the adversary’s
    observation may be corrupted over a noisy discrete memoryless channel. Through
    the adversary’s myopicity, one can unify the slew of different adversary models,
    ranging from the omniscient adversary to one that is completely blind to the transmission
    (the latter is the well known oblivious model where the capacity is fully characterized).In
    this work, we present new results on the capacity under both the omniscient and
    myopic adversary models. We completely characterize the positive capacity threshold
    over general AVCs with omniscient adversaries. The characterization is in terms
    of two key combinatorial objects: the set of completely positive distributions
    and the CP-confusability set. For omniscient AVCs with positive capacity, we present
    non-trivial lower and upper bounds on the capacity; unlike some of the previous
    bounds, our bounds hold under fairly general input and jamming constraints. Our
    lower bound improves upon the generalized Gilbert-Varshamov bound for general
    AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known
    for binary and q-ary alphabets). For the myopic AVCs, we build on prior results
    known for the so-called sufficiently myopic model, and present new results on
    the positive rate communication threshold over the so-called insufficiently myopic
    regime (a completely insufficient myopic adversary specializes to an omniscient
    adversary). We present interesting examples for the widely studied models of adversarial
    bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive
    adversarial noise as well as random noise, we completely characterize the omniscient
    model capacity when the random noise is sufficiently large vis-a-vis the adversary’s
    budget.'
article_processing_charge: No
author:
- first_name: Anuj Kumar
  full_name: Yadav, Anuj Kumar
  last_name: Yadav
- first_name: Mohammadreza
  full_name: Alimohammadi, Mohammadreza
  last_name: Alimohammadi
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Amitalok J.
  full_name: Budkuley, Amitalok J.
  last_name: Budkuley
- first_name: Sidharth
  full_name: Jaggi, Sidharth
  last_name: Jaggi
citation:
  ama: 'Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. New results on AVCs
    with omniscient and myopic adversaries. In: <i>2022 IEEE International Symposium
    on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers;
    2022:2535-2540. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834632">10.1109/ISIT50566.2022.9834632</a>'
  apa: 'Yadav, A. K., Alimohammadi, M., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S.
    (2022). New results on AVCs with omniscient and myopic adversaries. In <i>2022
    IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2535–2540).
    Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/ISIT50566.2022.9834632">https://doi.org/10.1109/ISIT50566.2022.9834632</a>'
  chicago: Yadav, Anuj Kumar, Mohammadreza Alimohammadi, Yihan Zhang, Amitalok J.
    Budkuley, and Sidharth Jaggi. “New Results on AVCs with Omniscient and Myopic
    Adversaries.” In <i>2022 IEEE International Symposium on Information Theory</i>,
    2022:2535–40. Institute of Electrical and Electronics Engineers, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834632">https://doi.org/10.1109/ISIT50566.2022.9834632</a>.
  ieee: A. K. Yadav, M. Alimohammadi, Y. Zhang, A. J. Budkuley, and S. Jaggi, “New
    results on AVCs with omniscient and myopic adversaries,” in <i>2022 IEEE International
    Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2535–2540.
  ista: 'Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. 2022. New results
    on AVCs with omniscient and myopic adversaries. 2022 IEEE International Symposium
    on Information Theory. ISIT: Internation Symposium on Information Theory vol.
    2022, 2535–2540.'
  mla: Yadav, Anuj Kumar, et al. “New Results on AVCs with Omniscient and Myopic Adversaries.”
    <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute
    of Electrical and Electronics Engineers, 2022, pp. 2535–40, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834632">10.1109/ISIT50566.2022.9834632</a>.
  short: A.K. Yadav, M. Alimohammadi, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022
    IEEE International Symposium on Information Theory, Institute of Electrical and
    Electronics Engineers, 2022, pp. 2535–2540.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:06Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2023-02-13T09:00:14Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834632
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 2535-2540
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: New results on AVCs with omniscient and myopic adversaries
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12018'
abstract:
- lang: eng
  text: We study the problem of characterizing the maximal rates of list decoding
    in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and
    real N > 0, we say that a subset C⊂Rn is an (N,L – 1)-multiple packing or an (N,L–
    1)-list decodable code if every Euclidean ball of radius nN−−−√ in ℝ n contains
    no more than L − 1 points of C. We study this problem with and without ℓ 2 norm
    constraints on C, and derive the best-known lower bounds on the maximal rate for
    (N,L−1) multiple packing. Our bounds are obtained via error exponents for list
    decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious
    inequality which relates the error exponent, a quantity of average-case nature,
    to the list-decoding radius, a quantity of worst-case nature. We derive various
    bounds on the error exponent for list decoding in both bounded and unbounded settings
    which could be of independent interest beyond multiple packing.
article_processing_charge: No
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
citation:
  ama: 'Zhang Y, Vatedka S. Lower bounds on list decoding capacity using error exponents.
    In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022.
    Institute of Electrical and Electronics Engineers; 2022:1324-1329. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834815">10.1109/ISIT50566.2022.9834815</a>'
  apa: 'Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds on list decoding capacity
    using error exponents. In <i>2022 IEEE International Symposium on Information
    Theory</i> (Vol. 2022, pp. 1324–1329). Espoo, Finland: Institute of Electrical
    and Electronics Engineers. <a href="https://doi.org/10.1109/ISIT50566.2022.9834815">https://doi.org/10.1109/ISIT50566.2022.9834815</a>'
  chicago: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity
    Using Error Exponents.” In <i>2022 IEEE International Symposium on Information
    Theory</i>, 2022:1324–29. Institute of Electrical and Electronics Engineers, 2022.
    <a href="https://doi.org/10.1109/ISIT50566.2022.9834815">https://doi.org/10.1109/ISIT50566.2022.9834815</a>.
  ieee: Y. Zhang and S. Vatedka, “Lower bounds on list decoding capacity using error
    exponents,” in <i>2022 IEEE International Symposium on Information Theory</i>,
    Espoo, Finland, 2022, vol. 2022, pp. 1324–1329.
  ista: 'Zhang Y, Vatedka S. 2022. Lower bounds on list decoding capacity using error
    exponents. 2022 IEEE International Symposium on Information Theory. ISIT: Internation
    Symposium on Information Theory vol. 2022, 1324–1329.'
  mla: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity
    Using Error Exponents.” <i>2022 IEEE International Symposium on Information Theory</i>,
    vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–29,
    doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834815">10.1109/ISIT50566.2022.9834815</a>.
  short: Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information
    Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–1329.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:06Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2023-02-13T09:02:06Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834815
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 1324-1329
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds on list decoding capacity using error exponents
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12019'
abstract:
- lang: eng
  text: This paper studies combinatorial properties of codes for the Z-channel. A
    Z-channel with error fraction τ takes as input a length-n binary codeword and
    injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that
    only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L
    − 1)-list-decodable code for the Z-channel with error fraction τ has exponential
    (in n) size if τ is less than a critical value that we call the Plotkin point
    and has constant size if τ is larger than the threshold. The (L−1)-list-decoding
    Plotkin point is known to be L−1L−1−L−LL−1. In this paper, we show that the largest
    (L−1)-list-decodable code ε-above the Plotkin point has size Θ L (ε −3/2 ) for
    any L − 1 ≥ 1.
article_processing_charge: No
author:
- first_name: Nikita
  full_name: Polyanskii, Nikita
  last_name: Polyanskii
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
citation:
  ama: 'Polyanskii N, Zhang Y. List-decodable zero-rate codes for the Z-channel. In:
    <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute
    of Electrical and Electronics Engineers; 2022:2553-2558. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834829">10.1109/ISIT50566.2022.9834829</a>'
  apa: 'Polyanskii, N., &#38; Zhang, Y. (2022). List-decodable zero-rate codes for
    the Z-channel. In <i>2022 IEEE International Symposium on Information Theory</i>
    (Vol. 2022, pp. 2553–2558). Espoo, Finland: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/ISIT50566.2022.9834829">https://doi.org/10.1109/ISIT50566.2022.9834829</a>'
  chicago: Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for
    the Z-Channel.” In <i>2022 IEEE International Symposium on Information Theory</i>,
    2022:2553–58. Institute of Electrical and Electronics Engineers, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834829">https://doi.org/10.1109/ISIT50566.2022.9834829</a>.
  ieee: N. Polyanskii and Y. Zhang, “List-decodable zero-rate codes for the Z-channel,”
    in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland,
    2022, vol. 2022, pp. 2553–2558.
  ista: 'Polyanskii N, Zhang Y. 2022. List-decodable zero-rate codes for the Z-channel.
    2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium
    on Information Theory vol. 2022, 2553–2558.'
  mla: Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the
    Z-Channel.” <i>2022 IEEE International Symposium on Information Theory</i>, vol.
    2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–58, doi:<a
    href="https://doi.org/10.1109/ISIT50566.2022.9834829">10.1109/ISIT50566.2022.9834829</a>.
  short: N. Polyanskii, Y. Zhang, in:, 2022 IEEE International Symposium on Information
    Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–2558.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: Internation Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:07Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2023-02-13T09:02:18Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834829
intvolume: '      2022'
language:
- iso: eng
month: '08'
oa_version: None
page: 2553-2558
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: List-decodable zero-rate codes for the Z-channel
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12273'
abstract:
- lang: eng
  text: We study communication in the presence of a jamming adversary where quadratic
    power constraints are imposed on the transmitter and the jammer. The jamming signal
    is allowed to be a function of the codebook, and a noncausal but noisy observation
    of the transmitted codeword. For a certain range of the noise-to-signal ratios
    (NSRs) of the transmitter and the jammer, we are able to characterize the capacity
    of this channel under deterministic encoding or stochastic encoding, i.e., with
    no common randomness between the encoder/decoder pair. For the remaining NSR regimes,
    we determine the capacity under the assumption of a small amount of common randomness
    (at most 2log(n) bits in one sub-regime, and at most Ω(n) bits in the other sub-regime)
    available to the encoder-decoder pair. Our proof techniques involve a novel myopic
    list-decoding result for achievability, and a Plotkin-type push attack for the
    converse in a subregion of the NSRs, both of which may be of independent interest.
    We also give bounds on the strong secrecy capacity of this channel assuming that
    the jammer is simultaneously eavesdropping.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
- first_name: Shashank
  full_name: Vatedka, Shashank
  last_name: Vatedka
- first_name: Sidharth
  full_name: Jaggi, Sidharth
  last_name: Jaggi
- first_name: Anand D.
  full_name: Sarwate, Anand D.
  last_name: Sarwate
citation:
  ama: Zhang Y, Vatedka S, Jaggi S, Sarwate AD. Quadratically constrained myopic adversarial
    channels. <i>IEEE Transactions on Information Theory</i>. 2022;68(8):4901-4948.
    doi:<a href="https://doi.org/10.1109/tit.2022.3167554">10.1109/tit.2022.3167554</a>
  apa: Zhang, Y., Vatedka, S., Jaggi, S., &#38; Sarwate, A. D. (2022). Quadratically
    constrained myopic adversarial channels. <i>IEEE Transactions on Information Theory</i>.
    Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/tit.2022.3167554">https://doi.org/10.1109/tit.2022.3167554</a>
  chicago: Zhang, Yihan, Shashank Vatedka, Sidharth Jaggi, and Anand D. Sarwate. “Quadratically
    Constrained Myopic Adversarial Channels.” <i>IEEE Transactions on Information
    Theory</i>. Institute of Electrical and Electronics Engineers, 2022. <a href="https://doi.org/10.1109/tit.2022.3167554">https://doi.org/10.1109/tit.2022.3167554</a>.
  ieee: Y. Zhang, S. Vatedka, S. Jaggi, and A. D. Sarwate, “Quadratically constrained
    myopic adversarial channels,” <i>IEEE Transactions on Information Theory</i>,
    vol. 68, no. 8. Institute of Electrical and Electronics Engineers, pp. 4901–4948,
    2022.
  ista: Zhang Y, Vatedka S, Jaggi S, Sarwate AD. 2022. Quadratically constrained myopic
    adversarial channels. IEEE Transactions on Information Theory. 68(8), 4901–4948.
  mla: Zhang, Yihan, et al. “Quadratically Constrained Myopic Adversarial Channels.”
    <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 8, Institute of Electrical
    and Electronics Engineers, 2022, pp. 4901–48, doi:<a href="https://doi.org/10.1109/tit.2022.3167554">10.1109/tit.2022.3167554</a>.
  short: Y. Zhang, S. Vatedka, S. Jaggi, A.D. Sarwate, IEEE Transactions on Information
    Theory 68 (2022) 4901–4948.
date_created: 2023-01-16T10:01:19Z
date_published: 2022-08-01T00:00:00Z
date_updated: 2023-08-04T10:08:49Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/tit.2022.3167554
external_id:
  arxiv:
  - '1801.05951'
  isi:
  - '000838527100004'
intvolume: '        68'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1801.05951
month: '08'
oa: 1
oa_version: Preprint
page: 4901-4948
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1557-9654
  issn:
  - 0018-9448
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quadratically constrained myopic adversarial channels
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...