---
_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: 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: Internation
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: 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: '12012'
abstract:
- lang: eng
text: This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We
generalize a previous framework for designing utility-optimal differentially private
(DP) mechanisms via graphs, where datasets are vertices in the graph and edges
represent dataset neighborhood. The boundary set contains datasets where an individual’s
response changes the binary-valued query compared to its neighbors. Previous work
was limited to the homogeneous case where the privacy parameter ε across all datasets
was the same and the mechanism at boundary datasets was identical. In our work,
the mechanism can take different distributions at the boundary and the privacy
parameter ε is a function of neighboring datasets, which recovers an earlier definition
of personalized DP as special case. The problem is how to extend the mechanism,
which is only defined at the boundary set, to other datasets in the graph in a
computationally efficient and utility optimal manner. Using the concept of strongest
induced DP condition we solve this problem efficiently in polynomial time (in
the size of the graph).
article_processing_charge: No
arxiv: 1
author:
- first_name: Sahel
full_name: Torkamani, Sahel
id: 0503e7f8-2d05-11ed-aa17-db0640c720fc
last_name: Torkamani
- first_name: Javad B.
full_name: Ebrahimi, Javad B.
last_name: Ebrahimi
- first_name: Parastoo
full_name: Sadeghi, Parastoo
last_name: Sadeghi
- first_name: Rafael G.L.
full_name: D'Oliveira, Rafael G.L.
last_name: D'Oliveira
- first_name: Muriel
full_name: Médard, Muriel
last_name: Médard
citation:
ama: 'Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. Heterogeneous
differential privacy via graphs. In: 2022 IEEE International Symposium on Information
Theory. Vol 2022. IEEE; 2022:1623-1628. doi:10.1109/ISIT50566.2022.9834711'
apa: 'Torkamani, S., Ebrahimi, J. B., Sadeghi, P., D’Oliveira, R. G. L., & Médard,
M. (2022). Heterogeneous differential privacy via graphs. In 2022 IEEE International
Symposium on Information Theory (Vol. 2022, pp. 1623–1628). Espoo, Finland:
IEEE. https://doi.org/10.1109/ISIT50566.2022.9834711'
chicago: Torkamani, Sahel, Javad B. Ebrahimi, Parastoo Sadeghi, Rafael G.L. D’Oliveira,
and Muriel Médard. “Heterogeneous Differential Privacy via Graphs.” In 2022
IEEE International Symposium on Information Theory, 2022:1623–28. IEEE, 2022.
https://doi.org/10.1109/ISIT50566.2022.9834711.
ieee: S. Torkamani, J. B. Ebrahimi, P. Sadeghi, R. G. L. D’Oliveira, and M. Médard,
“Heterogeneous differential privacy via graphs,” in 2022 IEEE International
Symposium on Information Theory, Espoo, Finland, 2022, vol. 2022, pp. 1623–1628.
ista: 'Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. 2022. Heterogeneous
differential privacy via graphs. 2022 IEEE International Symposium on Information
Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 1623–1628.'
mla: Torkamani, Sahel, et al. “Heterogeneous Differential Privacy via Graphs.” 2022
IEEE International Symposium on Information Theory, vol. 2022, IEEE, 2022,
pp. 1623–28, doi:10.1109/ISIT50566.2022.9834711.
short: S. Torkamani, J.B. Ebrahimi, P. Sadeghi, R.G.L. D’Oliveira, M. Médard, in:,
2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 1623–1628.
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:28:35Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834711
external_id:
arxiv:
- '2203.15429'
intvolume: ' 2022'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2203.15429
month: '08'
oa: 1
oa_version: Preprint
page: 1623-1628
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: Heterogeneous differential privacy via graphs
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: 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: Internation 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: 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: 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: Internation 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: 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: 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: Internation 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: 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: '12016'
abstract:
- lang: eng
text: We consider the problem of coded distributed computing using polar codes.
The average execution time of a coded computing system is related to the error
probability for transmission over the binary erasure channel in recent work by
Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes
is investigated. In this paper, we focus on polar codes and unveil a connection
between the average execution time and the scaling exponent μ of the family of
codes. In the finite-length characterization of polar codes, the scaling exponent
is a key object capturing the speed of convergence to capacity. In particular,
we show that (i) the gap between the normalized average execution time of polar
codes and that of optimal MDS codes is O(n –1/μ ), and (ii) this upper bound can
be improved to roughly O(n –1/2 ) by considering polar codes with large kernels.
We conjecture that these bounds could be improved to O(n –2/μ ) and O(n –1 ),
respectively, and provide a heuristic argument as well as numerical evidence supporting
this view.
acknowledgement: D. Fathollahi and M. Mondelli were partially supported by the 2019
Lopez-Loreta Prize. The authors thank Hamed Hassani and Hessam Mahdavifar for helpful
discussions.
article_processing_charge: No
arxiv: 1
author:
- first_name: Dorsa
full_name: Fathollahi, Dorsa
last_name: Fathollahi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Fathollahi D, Mondelli M. Polar coded computing: The role of the scaling exponent.
In: 2022 IEEE International Symposium on Information Theory. Vol 2022.
IEEE; 2022:2154-2159. doi:10.1109/ISIT50566.2022.9834712'
apa: 'Fathollahi, D., & Mondelli, M. (2022). Polar coded computing: The role
of the scaling exponent. In 2022 IEEE International Symposium on Information
Theory (Vol. 2022, pp. 2154–2159). Espoo, Finland: IEEE. https://doi.org/10.1109/ISIT50566.2022.9834712'
chicago: 'Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role
of the Scaling Exponent.” In 2022 IEEE International Symposium on Information
Theory, 2022:2154–59. IEEE, 2022. https://doi.org/10.1109/ISIT50566.2022.9834712.'
ieee: 'D. Fathollahi and M. Mondelli, “Polar coded computing: The role of the scaling
exponent,” in 2022 IEEE International Symposium on Information Theory,
Espoo, Finland, 2022, vol. 2022, pp. 2154–2159.'
ista: 'Fathollahi D, Mondelli M. 2022. Polar coded computing: The role of the scaling
exponent. 2022 IEEE International Symposium on Information Theory. ISIT: Internation
Symposium on Information Theory vol. 2022, 2154–2159.'
mla: 'Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of
the Scaling Exponent.” 2022 IEEE International Symposium on Information Theory,
vol. 2022, IEEE, 2022, pp. 2154–59, doi:10.1109/ISIT50566.2022.9834712.'
short: D. Fathollahi, M. Mondelli, in:, 2022 IEEE International Symposium on Information
Theory, IEEE, 2022, pp. 2154–2159.
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: 2024-09-10T13:03:17Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834712
external_id:
arxiv:
- '2201.10082'
intvolume: ' 2022'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2201.10082
month: '08'
oa: 1
oa_version: Preprint
page: 2154-2159
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
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: 'Polar coded computing: The role of the scaling exponent'
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: 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: 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: 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: Internation
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: 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:
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: Internation 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: 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'
...