---
OA_type: closed access
_id: '20667'
abstract:
- lang: eng
text: We explore the problem of mean estimation for a high-dimensional binary symmetric
Gaussian mixture model, where the label (sign) follows a time-inhomogeneous Markov
chain. We propose a spectral estimator based on a partition of a subset of the
samples to blocks. We develop a computationally efficient algorithm to find the
optimal blocks, and derive minimax lower bounds on the estimation loss of any
estimator, which establish the effectiveness of our proposed estimator. The resulting
minimax rate illuminates the interplay between the sample size, dimension, signal
strength, and the memory on the loss.
acknowledgement: The research of A.K. and N.W. was supported by the Israel Science
Foundation (ISF), grant no. 1782/22.
article_processing_charge: No
author:
- first_name: Abd
full_name: El Latif Kadry, Abd
last_name: El Latif Kadry
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
- first_name: Nir
full_name: Weinberger, Nir
last_name: Weinberger
citation:
ama: 'El Latif Kadry A, Zhang Y, Weinberger N. Mean estimation in high-dimensional
binary timeinhomogeneous Markov Gaussian mixture models. In: 2025 IEEE International
Symposium on Information Theory Proceedings. IEEE; 2025. doi:10.1109/ISIT63088.2025.11195426'
apa: 'El Latif Kadry, A., Zhang, Y., & Weinberger, N. (2025). Mean estimation
in high-dimensional binary timeinhomogeneous Markov Gaussian mixture models. In
2025 IEEE International Symposium on Information Theory Proceedings. Ann
Arbor, MI, United States: IEEE. https://doi.org/10.1109/ISIT63088.2025.11195426'
chicago: El Latif Kadry, Abd, Yihan Zhang, and Nir Weinberger. “Mean Estimation
in High-Dimensional Binary Timeinhomogeneous Markov Gaussian Mixture Models.”
In 2025 IEEE International Symposium on Information Theory Proceedings.
IEEE, 2025. https://doi.org/10.1109/ISIT63088.2025.11195426.
ieee: A. El Latif Kadry, Y. Zhang, and N. Weinberger, “Mean estimation in high-dimensional
binary timeinhomogeneous Markov Gaussian mixture models,” in 2025 IEEE International
Symposium on Information Theory Proceedings, Ann Arbor, MI, United States,
2025.
ista: 'El Latif Kadry A, Zhang Y, Weinberger N. 2025. Mean estimation in high-dimensional
binary timeinhomogeneous Markov Gaussian mixture models. 2025 IEEE International
Symposium on Information Theory Proceedings. ISIT: International Symposium on
Information Theory.'
mla: El Latif Kadry, Abd, et al. “Mean Estimation in High-Dimensional Binary Timeinhomogeneous
Markov Gaussian Mixture Models.” 2025 IEEE International Symposium on Information
Theory Proceedings, IEEE, 2025, doi:10.1109/ISIT63088.2025.11195426.
short: A. El Latif Kadry, Y. Zhang, N. Weinberger, in:, 2025 IEEE International
Symposium on Information Theory Proceedings, IEEE, 2025.
conference:
end_date: 2025-06-27
location: Ann Arbor, MI, United States
name: 'ISIT: International Symposium on Information Theory'
start_date: 2025-06-22
date_created: 2025-11-23T23:01:39Z
date_published: 2025-10-20T00:00:00Z
date_updated: 2025-11-24T08:53:34Z
day: '20'
department:
- _id: MaMo
doi: 10.1109/ISIT63088.2025.11195426
language:
- iso: eng
month: '10'
oa_version: None
publication: 2025 IEEE International Symposium on Information Theory Proceedings
publication_identifier:
isbn:
- '9798331543990'
issn:
- 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Mean estimation in high-dimensional binary timeinhomogeneous Markov Gaussian
mixture models
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
PlanS_conform: '1'
_id: '20734'
abstract:
- lang: eng
text: We consider the problem of parameter estimation in a high-dimensional generalized
linear model. Spectral methods obtained via the principal eigenvector of a suitable
data-dependent matrix provide a simple yet surprisingly effective solution. However,
despite their wide use, a rigorous performance characterization, as well as a
principled way to preprocess the data, are available only for unstructured (i.i.d.
Gaussian and Haar orthogonal) designs. In contrast, real-world data matrices are
highly structured and exhibit non-trivial correlations. To address the problem,
we consider correlated Gaussian designs capturing the anisotropic nature of the
features via a covariance matrix Σ. Our main result is a precise asymptotic characterization
of the performance of spectral estimators. This allows us to identify the optimal
preprocessing that minimizes the number of samples needed for parameter estimation.
Surprisingly, such preprocessing is universal across a broad set of designs, which
partly addresses a conjecture on optimal spectral estimators for rotationally
invariant models. Our principled approach vastly improves upon previous heuristic
methods, including for designs common in computational imaging and genetics. The
proposed methodology, based on approximate message passing, is broadly applicable
and opens the way to the precise characterization of spiked matrices and of the
corresponding spectral methods in a variety of settings.
acknowledgement: "This work was done when Y. Z. and H. C. J. were at the Institute
of Science and Technology Austria. Y. Z. thanks Hugo Latourelle-Vigeant for bringing
[53] to the authors’ attention.\r\nY. Z. and M. M. are partially supported by the
2019 Lopez-Loreta Prize and by the Interdisciplinary Projects Committee (IPC) at
ISTA. H. C. J. is supported by the ERC Advanced Grant “RMTBeyond” No. 101020331."
article_processing_charge: No
article_type: original
author:
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
- first_name: Hong Chang
full_name: Ji, Hong Chang
last_name: Ji
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Zhang Y, Ji HC, Venkataramanan R, Mondelli M. Spectral estimators for structured
generalized linear models via approximate message passing. Mathematical Statistics
and Learning. 2025;8(3-4):193-304. doi:10.4171/MSL/52
apa: Zhang, Y., Ji, H. C., Venkataramanan, R., & Mondelli, M. (2025). Spectral
estimators for structured generalized linear models via approximate message passing.
Mathematical Statistics and Learning. EMS Press. https://doi.org/10.4171/MSL/52
chicago: Zhang, Yihan, Hong Chang Ji, Ramji Venkataramanan, and Marco Mondelli.
“Spectral Estimators for Structured Generalized Linear Models via Approximate
Message Passing.” Mathematical Statistics and Learning. EMS Press, 2025.
https://doi.org/10.4171/MSL/52.
ieee: Y. Zhang, H. C. Ji, R. Venkataramanan, and M. Mondelli, “Spectral estimators
for structured generalized linear models via approximate message passing,” Mathematical
Statistics and Learning, vol. 8, no. 3–4. EMS Press, pp. 193–304, 2025.
ista: Zhang Y, Ji HC, Venkataramanan R, Mondelli M. 2025. Spectral estimators for
structured generalized linear models via approximate message passing. Mathematical
Statistics and Learning. 8(3–4), 193–304.
mla: Zhang, Yihan, et al. “Spectral Estimators for Structured Generalized Linear
Models via Approximate Message Passing.” Mathematical Statistics and Learning,
vol. 8, no. 3–4, EMS Press, 2025, pp. 193–304, doi:10.4171/MSL/52.
short: Y. Zhang, H.C. Ji, R. Venkataramanan, M. Mondelli, Mathematical Statistics
and Learning 8 (2025) 193–304.
corr_author: '1'
date_created: 2025-12-07T23:02:02Z
date_published: 2025-09-02T00:00:00Z
date_updated: 2025-12-09T13:53:31Z
day: '02'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.4171/MSL/52
file:
- access_level: open_access
checksum: 55a1bd9c1b6b0198c42504fb94f4ad4c
content_type: application/pdf
creator: dernst
date_created: 2025-12-09T13:50:03Z
date_updated: 2025-12-09T13:50:03Z
file_id: '20752'
file_name: 2025_MathStatLearning_Zhang.pdf
file_size: 1379626
relation: main_file
success: 1
file_date_updated: 2025-12-09T13:50:03Z
has_accepted_license: '1'
intvolume: ' 8'
issue: 3-4
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 193-304
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Mathematical Statistics and Learning
publication_identifier:
eissn:
- 2520-2324
issn:
- 2520-2316
publication_status: published
publisher: EMS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Spectral estimators for structured generalized linear models via approximate
message passing
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '19281'
abstract:
- lang: eng
text: "In this work, we consider the list-decodability and list-recoverability of
codes in the zero-rate regime. Briefly, a code \U0001D49E ⊆ [q]ⁿ is (p,\U0001D4C1,L)-list-recoverable
if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = \U0001D4C1,
the number of codewords c ∈ \U0001D49E such that c_i ∉ Y_i for at most pn choices
of i ∈ [n] is less than L; list-decoding is the special case of \U0001D4C1 = 1.
In recent work by Resch, Yuan and Zhang (ICALP 2023) the zero-rate threshold for
list-recovery was determined for all parameters: that is, the work explicitly
computes p_*: = p_*(q,\U0001D4C1,L) with the property that for all ε > 0 (a) there
exist positive-rate (p_*-ε,\U0001D4C1,L)-list-recoverable codes, and (b) any (p_*+ε,\U0001D4C1,L)-list-recoverable
code has rate 0. In fact, in the latter case the code has constant size, independent
on n. However, the constant size in their work is quite large in 1/ε, at least
|\U0001D49E| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that
for all choices of q,\U0001D4C1 and L with q ≥ 3, any (p_*+ε,\U0001D4C1,L)-list-recoverable
code must have size O_{q,\U0001D4C1,L}(1/ε), and furthermore this upper bound
is complemented by a matching lower bound Ω_{q,\U0001D4C1,L}(1/ε). This greatly
generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf. Theory 2018) which
focused only on the case of binary alphabet (and thus necessarily only list-decoding).
We remark that we can in fact recover the same result for q = 2 and even L, as
obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work.
\r\nOur main technical contribution is to (a) properly define a linear programming
relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate
that a certain function defined on a q-ary probability simplex is maximized by
the uniform distribution. This represents the core challenge in generalizing to
larger q (as a binary simplex can be naturally identified with a one-dimensional
interval). We can subsequently re-utilize certain Schur convexity and convexity
properties established for a related function by Resch, Yuan and Zhang along with
ideas of Alon, Bukh and Polyanskiy."
acknowledgement: "The research of C. Yuan was support in part by the National Key
R&D Program of China\r\nunder Grant 2023YFE0123900 and Natural Science Foundation
of Shanghai under the 2024 Shanghai Action Plan for Science, Technology and Innovation
Grant 24BC3200700. The research of N. Resch is supported in part by an NWO (Dutch
Research Council) grant with number C.2324.0590, and this work was done in part
while he was visiting the Simons Institute for the Theory of Computing, supported
by DOE grant #DE-SC0024124."
alternative_title:
- LIPIcs
article_number: '82'
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. Tight bounds on list-decodable and list-recoverable
zero-rate codes. In: 16th Innovations in Theoretical Computer Science Conference.
Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ITCS.2025.82'
apa: 'Resch, N., Yuan, C., & Zhang, Y. (2025). Tight bounds on list-decodable
and list-recoverable zero-rate codes. In 16th Innovations in Theoretical Computer
Science Conference (Vol. 325). New York, NY, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2025.82'
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable
and List-Recoverable Zero-Rate Codes.” In 16th Innovations in Theoretical Computer
Science Conference, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.82.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable
zero-rate codes,” in 16th Innovations in Theoretical Computer Science Conference,
New York, NY, United States, 2025, vol. 325.
ista: 'Resch N, Yuan C, Zhang Y. 2025. Tight bounds on list-decodable and list-recoverable
zero-rate codes. 16th Innovations in Theoretical Computer Science Conference.
ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 325, 82.'
mla: Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable
Zero-Rate Codes.” 16th Innovations in Theoretical Computer Science Conference,
vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ITCS.2025.82.
short: N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer
Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-01-10
location: New York, NY, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2025-01-07
corr_author: '1'
date_created: 2025-03-02T23:01:53Z
date_published: 2025-02-11T00:00:00Z
date_updated: 2025-09-30T10:42:35Z
day: '11'
ddc:
- '510'
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ITCS.2025.82
external_id:
arxiv:
- '2309.01800'
isi:
- '001532717300082'
file:
- access_level: open_access
checksum: df3921ddf1b360b07f43d427fea51242
content_type: application/pdf
creator: dernst
date_created: 2025-03-04T09:35:57Z
date_updated: 2025-03-04T09:35:57Z
file_id: '19286'
file_name: 2025_LIPIcs_Resch.pdf
file_size: 898601
relation: main_file
success: 1
file_date_updated: 2025-03-04T09:35:57Z
has_accepted_license: '1'
intvolume: ' 325'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 16th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773614'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds on list-decodable and list-recoverable zero-rate codes
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 325
year: '2025'
...
---
_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.
acknowledgement: "The work of Yihan Zhang was supported by the European Union’s Horizon
2020 Research and Innovation Programme under Grant 682203-ERC-[Inf-Speed-Tradeoff].
The work of Shashank Vatedka was supported in part by the Core Research Grant from
the Science and\r\nEngineering Research Board, India, under Grant CRG/2022/004464;
and in\r\npart by the Department of Science and Technology (DST), India, under Grant\r\nDST/INT/RUS/RSF/P-41/2020
(TPN No. 65025)."
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. IEEE
Transactions on Information Theory. 2024;70(2):1008-1039. doi:10.1109/TIT.2023.3334032'
apa: 'Zhang, Y., & Vatedka, S. (2024). Multiple packing: Lower bounds via error
exponents. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2023.3334032'
chicago: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via
Error Exponents.” IEEE Transactions on Information Theory. IEEE, 2024.
https://doi.org/10.1109/TIT.2023.3334032.'
ieee: 'Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via error exponents,”
IEEE Transactions on Information Theory, vol. 70, no. 2. IEEE, pp. 1008–1039,
2024.'
ista: 'Zhang Y, Vatedka S. 2024. Multiple packing: Lower bounds via error exponents.
IEEE Transactions on Information Theory. 70(2), 1008–1039.'
mla: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Error
Exponents.” IEEE Transactions on Information Theory, vol. 70, no. 2, IEEE,
2024, pp. 1008–39, doi:10.1109/TIT.2023.3334032.'
short: Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 70 (2024) 1008–1039.
corr_author: '1'
date_created: 2023-12-10T23:01:00Z
date_published: 2024-02-01T00:00:00Z
date_updated: 2025-09-04T11:32:49Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TIT.2023.3334032
external_id:
arxiv:
- '2211.04408'
isi:
- '001166812100008'
intvolume: ' 70'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2211.04408
month: '02'
oa: 1
oa_version: Preprint
page: 1008-1039
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 error exponents'
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 70
year: '2024'
...
---
_id: '17895'
abstract:
- lang: eng
text: We propose a concatenated code construction for a class of discrete-alphabet
oblivious arbitrarily varying channels (AVCs) with cost constraints. The code
has time and space complexity polynomial in the blocklength n . It uses a Reed-Solomon
outer code, logarithmic blocklength random inner codes, and stochastic encoding
by permuting the codeword before transmission. When the channel satisfies a condition
called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability
originally due to Dobrushin and Stambler), we show that the code achieves a rate
that for a variety of oblivious AVCs (such as classically studied error/erasure
channels) match the known capacities.
acknowledgement: "The work of M. Langberg and A. D. Sarwate was supported in part
by the US NSF under awards CCF-1909451 and CCF1909468. B. K. Dey was supported in
part by the Bharti Centre\r\nfor Communication in IIT Bombay. "
article_processing_charge: No
author:
- first_name: B. K.
full_name: Dey, B. K.
last_name: Dey
- first_name: S.
full_name: Jaggi, S.
last_name: Jaggi
- first_name: M.
full_name: Langberg, M.
last_name: Langberg
- first_name: A. D.
full_name: Sarwate, A. D.
last_name: Sarwate
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
citation:
ama: 'Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Computationally efficient
codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In: Proceedings
of the 2024 IEEE International Symposium on Information Theory . Institute
of Electrical and Electronics Engineers; 2024:1586-1591. doi:10.1109/ISIT57864.2024.10619362'
apa: 'Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., & Zhang, Y. (2024).
Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable
oblivious AVCs. In Proceedings of the 2024 IEEE International Symposium on
Information Theory (pp. 1586–1591). Athens, Greece: Institute of Electrical
and Electronics Engineers. https://doi.org/10.1109/ISIT57864.2024.10619362'
chicago: Dey, B. K., S. Jaggi, M. Langberg, A. D. Sarwate, and Yihan Zhang. “Computationally
Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.”
In Proceedings of the 2024 IEEE International Symposium on Information Theory
, 1586–91. Institute of Electrical and Electronics Engineers, 2024. https://doi.org/10.1109/ISIT57864.2024.10619362.
ieee: B. K. Dey, S. Jaggi, M. Langberg, A. D. Sarwate, and Y. Zhang, “Computationally
efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs,”
in Proceedings of the 2024 IEEE International Symposium on Information Theory
, Athens, Greece, 2024, pp. 1586–1591.
ista: 'Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Computationally efficient
codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. Proceedings
of the 2024 IEEE International Symposium on Information Theory . ISIT: International
Symposium on Information Theory, 1586–1591.'
mla: Dey, B. K., et al. “Computationally Efficient Codes for Strongly Dobrushin-Stambler
Nonsymmetrizable Oblivious AVCs.” Proceedings of the 2024 IEEE International
Symposium on Information Theory , Institute of Electrical and Electronics
Engineers, 2024, pp. 1586–91, doi:10.1109/ISIT57864.2024.10619362.
short: B.K. Dey, S. Jaggi, M. Langberg, A.D. Sarwate, Y. Zhang, in:, Proceedings
of the 2024 IEEE International Symposium on Information Theory , Institute of
Electrical and Electronics Engineers, 2024, pp. 1586–1591.
conference:
end_date: 2024-07-12
location: Athens, Greece
name: 'ISIT: International Symposium on Information Theory'
start_date: 2024-07-07
date_created: 2024-09-08T22:01:12Z
date_published: 2024-08-19T00:00:00Z
date_updated: 2025-09-08T09:19:25Z
day: '19'
department:
- _id: MaMo
doi: 10.1109/ISIT57864.2024.10619362
external_id:
isi:
- '001304426901091'
isi: 1
language:
- iso: eng
month: '08'
oa_version: None
page: 1586-1591
publication: 'Proceedings of the 2024 IEEE International Symposium on Information
Theory '
publication_identifier:
isbn:
- '9798350382846'
issn:
- 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable
oblivious AVCs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_type: closed access
_id: '18652'
abstract:
- lang: eng
text: 'Over the last 70 years, information theory and coding has enabled communication
technologies that have had an astounding impact on our lives. This is possible
due to the match between encoding/decoding strategies and corresponding channel
models. Traditional studies of channels have taken one of two extremes: Shannon-theoretic
models are inherently average-case in which channel noise is governed by a memoryless
stochastic process, whereas coding-theoretic (referred to as “Hamming”) models
take a worst-case, adversarial, view of the noise. However, for several existing
and emerging communication systems the Shannon/average-case view may be too optimistic,
whereas the Hamming/worstcase view may be too pessimistic. This monograph takes
up the challenge of studying adversarial channel models that lie between the Shannon
and Hamming extremes.'
article_processing_charge: No
article_type: original
author:
- first_name: Bikash Kumar
full_name: Dey, Bikash Kumar
last_name: Dey
- 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
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
citation:
ama: 'Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Codes for adversaries: Between
worst-case and average-case jamming. Foundations and Trends in Communications
and Information Theory. 2024;21(3-4):300-588. doi:10.1561/0100000112'
apa: 'Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., & Zhang, Y. (2024).
Codes for adversaries: Between worst-case and average-case jamming. Foundations
and Trends in Communications and Information Theory. Now Publishers. https://doi.org/10.1561/0100000112'
chicago: 'Dey, Bikash Kumar, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate,
and Yihan Zhang. “Codes for Adversaries: Between Worst-Case and Average-Case Jamming.”
Foundations and Trends in Communications and Information Theory. Now Publishers,
2024. https://doi.org/10.1561/0100000112.'
ieee: 'B. K. Dey, S. Jaggi, M. Langberg, A. D. Sarwate, and Y. Zhang, “Codes for
adversaries: Between worst-case and average-case jamming,” Foundations and
Trends in Communications and Information Theory, vol. 21, no. 3–4. Now Publishers,
pp. 300–588, 2024.'
ista: 'Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Codes for adversaries:
Between worst-case and average-case jamming. Foundations and Trends in Communications
and Information Theory. 21(3–4), 300–588.'
mla: 'Dey, Bikash Kumar, et al. “Codes for Adversaries: Between Worst-Case and Average-Case
Jamming.” Foundations and Trends in Communications and Information Theory,
vol. 21, no. 3–4, Now Publishers, 2024, pp. 300–588, doi:10.1561/0100000112.'
short: B.K. Dey, S. Jaggi, M. Langberg, A.D. Sarwate, Y. Zhang, Foundations and
Trends in Communications and Information Theory 21 (2024) 300–588.
corr_author: '1'
date_created: 2024-12-15T23:01:50Z
date_published: 2024-12-03T00:00:00Z
date_updated: 2024-12-16T10:38:44Z
day: '03'
department:
- _id: MaMo
doi: 10.1561/0100000112
intvolume: ' 21'
issue: 3-4
language:
- iso: eng
month: '12'
oa_version: None
page: 300-588
publication: Foundations and Trends in Communications and Information Theory
publication_identifier:
eissn:
- 1567-2328
issn:
- 1567-2190
publication_status: published
publisher: Now Publishers
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Codes for adversaries: Between worst-case and average-case jamming'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '17330'
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 , ℓ, L ) q -recoverability is a generalization where we place radius pn Hamming
balls on every point of a combinatorial rectangle with side length ℓ and again
stipulate that there be less than L codewords. Our main contribution is to precisely
calculate the maximum value of p for which there exist infinite families of positive
rate ( p , ℓ, 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. Technically, proving the Plotkin bound boils down to demon-strating
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: Part of this work was done while Nicolas Resch was affiliated with
the Centrum Wiskunde & Informatica and supported in part by ERC H2020 grant No.74079
(ALGSTRONGCRYPTO). Chen Yuan is 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.
article_processing_charge: No
article_type: original
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. IEEE Transactions on Information Theory.
2024;70(9):6211-6238. doi:10.1109/TIT.2024.3430842
apa: Resch, N., Yuan, C., & Zhang, Y. (2024). Zero-rate thresholds and new capacity
bounds for list-decoding and list-recovery. IEEE Transactions on Information
Theory. IEEE. https://doi.org/10.1109/TIT.2024.3430842
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New
Capacity Bounds for List-Decoding and List-Recovery.” IEEE Transactions on
Information Theory. IEEE, 2024. https://doi.org/10.1109/TIT.2024.3430842.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery,” IEEE Transactions on Information Theory,
vol. 70, no. 9. IEEE, pp. 6211–6238, 2024.
ista: Resch N, Yuan C, Zhang Y. 2024. Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery. IEEE Transactions on Information Theory.
70(9), 6211–6238.
mla: Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding
and List-Recovery.” IEEE Transactions on Information Theory, vol. 70, no.
9, IEEE, 2024, pp. 6211–38, doi:10.1109/TIT.2024.3430842.
short: N. Resch, C. Yuan, Y. Zhang, IEEE Transactions on Information Theory 70 (2024)
6211–6238.
corr_author: '1'
date_created: 2024-07-28T22:01:10Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-09-08T08:31:53Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TIT.2024.3430842
external_id:
arxiv:
- '2210.07754'
isi:
- '001299623600019'
intvolume: ' 70'
isi: 1
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2210.07754
month: '09'
oa: 1
oa_version: Preprint
page: 6211-6238
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '14083'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 70
year: '2024'
...
---
_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: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.99'
apa: 'Resch, N., Yuan, C., & Zhang, Y. (2023). Zero-rate thresholds and new
capacity bounds for list-decoding and list-recovery. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.99'
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New
Capacity Bounds for List-Decoding and List-Recovery.” In 50th International
Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.99.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery,” in 50th International Colloquium on Automata,
Languages, and Programming, 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: 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.” 50th International Colloquium on Automata, Languages, and
Programming, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.ICALP.2023.99.
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: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:13Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-09-08T08:31:53Z
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'
related_material:
record:
- id: '17330'
relation: later_version
status: public
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.
IEEE Transactions on Information Theory. 2023;69(7):4513-4527. doi:10.1109/TIT.2023.3260950'
apa: 'Zhang, Y., & Vatedka, S. (2023). Multiple packing: Lower bounds via infinite
constellations. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2023.3260950'
chicago: 'Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via
Infinite Constellations.” IEEE Transactions on Information Theory. IEEE,
2023. https://doi.org/10.1109/TIT.2023.3260950.'
ieee: 'Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via infinite constellations,”
IEEE Transactions on Information Theory, 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.” IEEE Transactions on Information Theory, vol. 69, no.
7, IEEE, 2023, pp. 4513–27, doi:10.1109/TIT.2023.3260950.'
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: '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. IEEE Transactions on Information
Theory. 2023;69(10):6340-6357. doi:10.1109/TIT.2023.3292219
apa: Polyanskii, N., & Zhang, Y. (2023). Codes for the Z-channel. IEEE Transactions
on Information Theory. Institute of Electrical and Electronics Engineers.
https://doi.org/10.1109/TIT.2023.3292219
chicago: Polyanskii, Nikita, and Yihan Zhang. “Codes for the Z-Channel.” IEEE
Transactions on Information Theory. Institute of Electrical and Electronics
Engineers, 2023. https://doi.org/10.1109/TIT.2023.3292219.
ieee: N. Polyanskii and Y. Zhang, “Codes for the Z-channel,” IEEE Transactions
on Information Theory, 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.” IEEE Transactions
on Information Theory, vol. 69, no. 10, Institute of Electrical and Electronics
Engineers, 2023, pp. 6340–57, doi:10.1109/TIT.2023.3292219.
short: N. Polyanskii, Y. Zhang, IEEE Transactions on Information Theory 69 (2023)
6340–6357.
corr_author: '1'
date_created: 2023-07-23T22:01:14Z
date_published: 2023-07-04T00:00:00Z
date_updated: 2024-10-09T21:06:01Z
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: '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. IEEE Transactions
on Information Theory. 2023;69(7):4093-4127. doi:10.1109/tit.2023.3257239
apa: Zhang, Y. (2023). Zero-error communication over adversarial MACs. IEEE Transactions
on Information Theory. Institute of Electrical and Electronics Engineers.
https://doi.org/10.1109/tit.2023.3257239
chicago: Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” IEEE
Transactions on Information Theory. Institute of Electrical and Electronics
Engineers, 2023. https://doi.org/10.1109/tit.2023.3257239.
ieee: Y. Zhang, “Zero-error communication over adversarial MACs,” IEEE Transactions
on Information Theory, 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.” IEEE Transactions
on Information Theory, vol. 69, no. 7, Institute of Electrical and Electronics
Engineers, 2023, pp. 4093–127, doi:10.1109/tit.2023.3257239.
short: Y. Zhang, IEEE Transactions on Information Theory 69 (2023) 4093–4127.
corr_author: '1'
date_created: 2024-01-08T13:04:54Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-09-09T14:12:32Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/tit.2023.3257239
external_id:
arxiv:
- '2101.12426'
isi:
- '001017307000001'
intvolume: ' 69'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- first_name: Shashank
full_name: Vatedka, Shashank
last_name: Vatedka
citation:
ama: Zhang Y, Vatedka S. List decoding random Euclidean codes and Infinite constellations.
IEEE Transactions on Information Theory. 2022;68(12):7753-7786. doi:10.1109/TIT.2022.3189542
apa: Zhang, Y., & Vatedka, S. (2022). List decoding random Euclidean codes and
Infinite constellations. IEEE Transactions on Information Theory. IEEE.
https://doi.org/10.1109/TIT.2022.3189542
chicago: Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes
and Infinite Constellations.” IEEE Transactions on Information Theory.
IEEE, 2022. https://doi.org/10.1109/TIT.2022.3189542.
ieee: Y. Zhang and S. Vatedka, “List decoding random Euclidean codes and Infinite
constellations,” IEEE Transactions on Information Theory, 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.” IEEE Transactions on Information Theory, vol.
68, no. 12, IEEE, 2022, pp. 7753–86, doi:10.1109/TIT.2022.3189542.
short: Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 68 (2022) 7753–7786.
corr_author: '1'
date_created: 2022-07-24T22:01:42Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2024-10-09T21:02:55Z
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
orcid: 0000-0002-6465-6258
- 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: 2022 IEEE International Symposium on Information Theory.
Vol 2022. IEEE; 2022:2523-2528. doi:10.1109/ISIT50566.2022.9834709'
apa: 'Zhang, Y., Jaggi, S., Langberg, M., & Sarwate, A. D. (2022). The capacity
of causal adversarial channels. In 2022 IEEE International Symposium on Information
Theory (Vol. 2022, pp. 2523–2528). Espoo, Finland: IEEE. https://doi.org/10.1109/ISIT50566.2022.9834709'
chicago: Zhang, Yihan, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. “The
Capacity of Causal Adversarial Channels.” In 2022 IEEE International Symposium
on Information Theory, 2022:2523–28. IEEE, 2022. https://doi.org/10.1109/ISIT50566.2022.9834709.
ieee: Y. Zhang, S. Jaggi, M. Langberg, and A. D. Sarwate, “The capacity of causal
adversarial channels,” in 2022 IEEE International Symposium on Information
Theory, 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: International
Symposium on Information Theory vol. 2022, 2523–2528.'
mla: Zhang, Yihan, et al. “The Capacity of Causal Adversarial Channels.” 2022
IEEE International Symposium on Information Theory, vol. 2022, IEEE, 2022,
pp. 2523–28, doi:10.1109/ISIT50566.2022.9834709.
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: International 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: 2025-09-10T09:40:42Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834709
external_id:
arxiv:
- '2205.06708'
isi:
- '001254261902114'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- 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: 2022 IEEE International Symposium on Information
Theory. Vol 2022. IEEE; 2022:504-509. doi:10.1109/ISIT50566.2022.9834850'
apa: 'Joshi, P., Purkayastha, A., Zhang, Y., Budkuley, A. J., & Jaggi, S. (2022).
On the capacity of additive AVCs with feedback. In 2022 IEEE International
Symposium on Information Theory (Vol. 2022, pp. 504–509). Espoo, Finland:
IEEE. https://doi.org/10.1109/ISIT50566.2022.9834850'
chicago: Joshi, Pranav, Amritakshya Purkayastha, Yihan Zhang, Amitalok J. Budkuley,
and Sidharth Jaggi. “On the Capacity of Additive AVCs with Feedback.” In 2022
IEEE International Symposium on Information Theory, 2022:504–9. IEEE, 2022.
https://doi.org/10.1109/ISIT50566.2022.9834850.
ieee: P. Joshi, A. Purkayastha, Y. Zhang, A. J. Budkuley, and S. Jaggi, “On the
capacity of additive AVCs with feedback,” in 2022 IEEE International Symposium
on Information Theory, 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: International Symposium on Information Theory vol. 2022, 504–509.'
mla: Joshi, Pranav, et al. “On the Capacity of Additive AVCs with Feedback.” 2022
IEEE International Symposium on Information Theory, vol. 2022, IEEE, 2022,
pp. 504–09, doi:10.1109/ISIT50566.2022.9834850.
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: International 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: 2025-09-10T09:42:04Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834850
external_id:
isi:
- '001254261900085'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- first_name: Shashank
full_name: Vatedka, Shashank
last_name: Vatedka
citation:
ama: 'Zhang Y, Vatedka S. List-decodability of Poisson Point Processes. In: 2022
IEEE International Symposium on Information Theory. Vol 2022. IEEE; 2022:2559-2564.
doi:10.1109/ISIT50566.2022.9834512'
apa: 'Zhang, Y., & Vatedka, S. (2022). List-decodability of Poisson Point Processes.
In 2022 IEEE International Symposium on Information Theory (Vol. 2022,
pp. 2559–2564). Espoo, Finland: IEEE. https://doi.org/10.1109/ISIT50566.2022.9834512'
chicago: Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point
Processes.” In 2022 IEEE International Symposium on Information Theory,
2022:2559–64. IEEE, 2022. https://doi.org/10.1109/ISIT50566.2022.9834512.
ieee: Y. Zhang and S. Vatedka, “List-decodability of Poisson Point Processes,” in
2022 IEEE International Symposium on Information Theory, 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: International Symposium
on Information Theory vol. 2022, 2559–2564.'
mla: Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.”
2022 IEEE International Symposium on Information Theory, vol. 2022, IEEE,
2022, pp. 2559–64, doi:10.1109/ISIT50566.2022.9834512.
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: International 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: 2025-09-10T09:41:24Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834512
external_id:
isi:
- '001254261902120'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- first_name: Shashank
full_name: Vatedka, Shashank
last_name: Vatedka
citation:
ama: 'Zhang Y, Vatedka S. Lower bounds for multiple packing. In: 2022 IEEE International
Symposium on Information Theory. Vol 2022. IEEE; 2022:3085-3090. doi:10.1109/ISIT50566.2022.9834443'
apa: 'Zhang, Y., & Vatedka, S. (2022). Lower bounds for multiple packing. In
2022 IEEE International Symposium on Information Theory (Vol. 2022, pp.
3085–3090). Espoo, Finland: IEEE. https://doi.org/10.1109/ISIT50566.2022.9834443'
chicago: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.”
In 2022 IEEE International Symposium on Information Theory, 2022:3085–90.
IEEE, 2022. https://doi.org/10.1109/ISIT50566.2022.9834443.
ieee: Y. Zhang and S. Vatedka, “Lower bounds for multiple packing,” in 2022 IEEE
International Symposium on Information Theory, 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: International Symposium on Information
Theory vol. 2022, 3085–3090.'
mla: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” 2022
IEEE International Symposium on Information Theory, vol. 2022, IEEE, 2022,
pp. 3085–90, doi:10.1109/ISIT50566.2022.9834443.
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: International 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: 2025-09-10T09:44:24Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834443
external_id:
isi:
- '001254261903042'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- 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: 2022 IEEE International Symposium
on Information Theory. Vol 2022. Institute of Electrical and Electronics Engineers;
2022:2535-2540. doi:10.1109/ISIT50566.2022.9834632'
apa: 'Yadav, A. K., Alimohammadi, M., Zhang, Y., Budkuley, A. J., & Jaggi, S.
(2022). New results on AVCs with omniscient and myopic adversaries. In 2022
IEEE International Symposium on Information Theory (Vol. 2022, pp. 2535–2540).
Espoo, Finland: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT50566.2022.9834632'
chicago: Yadav, Anuj Kumar, Mohammadreza Alimohammadi, Yihan Zhang, Amitalok J.
Budkuley, and Sidharth Jaggi. “New Results on AVCs with Omniscient and Myopic
Adversaries.” In 2022 IEEE International Symposium on Information Theory,
2022:2535–40. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/ISIT50566.2022.9834632.
ieee: A. K. Yadav, M. Alimohammadi, Y. Zhang, A. J. Budkuley, and S. Jaggi, “New
results on AVCs with omniscient and myopic adversaries,” in 2022 IEEE International
Symposium on Information Theory, 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.”
2022 IEEE International Symposium on Information Theory, vol. 2022, Institute
of Electrical and Electronics Engineers, 2022, pp. 2535–40, doi:10.1109/ISIT50566.2022.9834632.
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: 2025-09-10T09:45:03Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834632
external_id:
isi:
- '001254261902116'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- 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: 2022 IEEE International Symposium on Information Theory. Vol 2022.
Institute of Electrical and Electronics Engineers; 2022:1324-1329. doi:10.1109/ISIT50566.2022.9834815'
apa: 'Zhang, Y., & Vatedka, S. (2022). Lower bounds on list decoding capacity
using error exponents. In 2022 IEEE International Symposium on Information
Theory (Vol. 2022, pp. 1324–1329). Espoo, Finland: Institute of Electrical
and Electronics Engineers. https://doi.org/10.1109/ISIT50566.2022.9834815'
chicago: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity
Using Error Exponents.” In 2022 IEEE International Symposium on Information
Theory, 2022:1324–29. Institute of Electrical and Electronics Engineers, 2022.
https://doi.org/10.1109/ISIT50566.2022.9834815.
ieee: Y. Zhang and S. Vatedka, “Lower bounds on list decoding capacity using error
exponents,” in 2022 IEEE International Symposium on Information Theory,
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: International
Symposium on Information Theory vol. 2022, 1324–1329.'
mla: Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity
Using Error Exponents.” 2022 IEEE International Symposium on Information Theory,
vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–29,
doi:10.1109/ISIT50566.2022.9834815.
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: International 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: 2025-09-10T09:45:40Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834815
external_id:
isi:
- '001254261901080'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
citation:
ama: 'Polyanskii N, Zhang Y. List-decodable zero-rate codes for the Z-channel. In:
2022 IEEE International Symposium on Information Theory. Vol 2022. Institute
of Electrical and Electronics Engineers; 2022:2553-2558. doi:10.1109/ISIT50566.2022.9834829'
apa: 'Polyanskii, N., & Zhang, Y. (2022). List-decodable zero-rate codes for
the Z-channel. In 2022 IEEE International Symposium on Information Theory
(Vol. 2022, pp. 2553–2558). Espoo, Finland: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/ISIT50566.2022.9834829'
chicago: Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for
the Z-Channel.” In 2022 IEEE International Symposium on Information Theory,
2022:2553–58. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/ISIT50566.2022.9834829.
ieee: N. Polyanskii and Y. Zhang, “List-decodable zero-rate codes for the Z-channel,”
in 2022 IEEE International Symposium on Information Theory, 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: International Symposium
on Information Theory vol. 2022, 2553–2558.'
mla: Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the
Z-Channel.” 2022 IEEE International Symposium on Information Theory, vol.
2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–58, doi:10.1109/ISIT50566.2022.9834829.
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: International 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: 2025-09-10T09:46:15Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834829
external_id:
isi:
- '001254261902119'
intvolume: ' 2022'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
orcid: 0000-0002-6465-6258
- 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. IEEE Transactions on Information Theory. 2022;68(8):4901-4948.
doi:10.1109/tit.2022.3167554
apa: Zhang, Y., Vatedka, S., Jaggi, S., & Sarwate, A. D. (2022). Quadratically
constrained myopic adversarial channels. IEEE Transactions on Information Theory.
Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/tit.2022.3167554
chicago: Zhang, Yihan, Shashank Vatedka, Sidharth Jaggi, and Anand D. Sarwate. “Quadratically
Constrained Myopic Adversarial Channels.” IEEE Transactions on Information
Theory. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/tit.2022.3167554.
ieee: Y. Zhang, S. Vatedka, S. Jaggi, and A. D. Sarwate, “Quadratically constrained
myopic adversarial channels,” IEEE Transactions on Information Theory,
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.”
IEEE Transactions on Information Theory, vol. 68, no. 8, Institute of Electrical
and Electronics Engineers, 2022, pp. 4901–48, doi:10.1109/tit.2022.3167554.
short: Y. Zhang, S. Vatedka, S. Jaggi, A.D. Sarwate, IEEE Transactions on Information
Theory 68 (2022) 4901–4948.
corr_author: '1'
date_created: 2023-01-16T10:01:19Z
date_published: 2022-08-01T00:00:00Z
date_updated: 2024-10-09T21:03:54Z
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'
...