[{"oa_version":"None","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","doi":"10.1109/ISIT63088.2025.11195426","day":"20","publication_status":"published","department":[{"_id":"MaMo"}],"date_published":"2025-10-20T00:00:00Z","month":"10","year":"2025","acknowledgement":"The research of A.K. and N.W. was supported by the Israel Science Foundation (ISF), grant no. 1782/22.","scopus_import":"1","citation":{"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.” <i>2025 IEEE International Symposium on Information Theory Proceedings</i>, IEEE, 2025, doi:<a href=\"https://doi.org/10.1109/ISIT63088.2025.11195426\">10.1109/ISIT63088.2025.11195426</a>.","chicago":"El Latif Kadry, Abd, Yihan Zhang, and Nir Weinberger. “Mean Estimation in High-Dimensional Binary Timeinhomogeneous Markov Gaussian Mixture Models.” In <i>2025 IEEE International Symposium on Information Theory Proceedings</i>. IEEE, 2025. <a href=\"https://doi.org/10.1109/ISIT63088.2025.11195426\">https://doi.org/10.1109/ISIT63088.2025.11195426</a>.","short":"A. El Latif Kadry, Y. Zhang, N. Weinberger, in:, 2025 IEEE International Symposium on Information Theory Proceedings, IEEE, 2025.","ama":"El Latif Kadry A, Zhang Y, Weinberger N. Mean estimation in high-dimensional binary timeinhomogeneous Markov Gaussian mixture models. In: <i>2025 IEEE International Symposium on Information Theory Proceedings</i>. IEEE; 2025. doi:<a href=\"https://doi.org/10.1109/ISIT63088.2025.11195426\">10.1109/ISIT63088.2025.11195426</a>","apa":"El Latif Kadry, A., Zhang, Y., &#38; Weinberger, N. (2025). Mean estimation in high-dimensional binary timeinhomogeneous Markov Gaussian mixture models. In <i>2025 IEEE International Symposium on Information Theory Proceedings</i>. Ann Arbor, MI, United States: IEEE. <a href=\"https://doi.org/10.1109/ISIT63088.2025.11195426\">https://doi.org/10.1109/ISIT63088.2025.11195426</a>","ieee":"A. El Latif Kadry, Y. Zhang, and N. Weinberger, “Mean estimation in high-dimensional binary timeinhomogeneous Markov Gaussian mixture models,” in <i>2025 IEEE International Symposium on Information Theory Proceedings</i>, Ann Arbor, MI, United States, 2025."},"publisher":"IEEE","status":"public","conference":{"start_date":"2025-06-22","name":"ISIT: International Symposium on Information Theory","end_date":"2025-06-27","location":"Ann Arbor, MI, United States"},"author":[{"full_name":"El Latif Kadry, Abd","last_name":"El Latif Kadry","first_name":"Abd"},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan"},{"full_name":"Weinberger, Nir","last_name":"Weinberger","first_name":"Nir"}],"OA_type":"closed access","_id":"20667","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Mean estimation in high-dimensional binary timeinhomogeneous Markov Gaussian mixture models","date_updated":"2025-11-24T08:53:34Z","type":"conference","publication_identifier":{"isbn":["9798331543990"],"issn":["2157-8095"]},"date_created":"2025-11-23T23:01:39Z","publication":"2025 IEEE International Symposium on Information Theory Proceedings","abstract":[{"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.","lang":"eng"}]},{"date_published":"2024-08-19T00:00:00Z","page":"3178-3183","article_processing_charge":"No","publisher":"Institute of Electrical and Electronics Engineers","year":"2024","_id":"17893","external_id":{"isi":["001304426903055"],"arxiv":["2403.10656"]},"isi":1,"author":[{"full_name":"Jin, Lifu","last_name":"Jin","first_name":"Lifu"},{"id":"9583e921-e1ad-11ec-9862-cef099626dc9","full_name":"Esposito, Amedeo Roberto","last_name":"Esposito","first_name":"Amedeo Roberto"},{"first_name":"Michael","full_name":"Gastpar, Michael","last_name":"Gastpar"}],"department":[{"_id":"MaMo"}],"publication_status":"published","doi":"10.1109/ISIT57864.2024.10619367","day":"19","corr_author":"1","month":"08","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Preprint","arxiv":1,"citation":{"ama":"Jin L, Esposito AR, Gastpar M. Properties of the strong data processing constant for Rényi divergence. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>. Institute of Electrical and Electronics Engineers; 2024:3178-3183. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">10.1109/ISIT57864.2024.10619367</a>","apa":"Jin, L., Esposito, A. R., &#38; Gastpar, M. (2024). Properties of the strong data processing constant for Rényi divergence. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i> (pp. 3178–3183). Athens, Greece: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">https://doi.org/10.1109/ISIT57864.2024.10619367</a>","ieee":"L. Jin, A. R. Esposito, and M. Gastpar, “Properties of the strong data processing constant for Rényi divergence,” in <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, Athens, Greece, 2024, pp. 3178–3183.","ista":"Jin L, Esposito AR, Gastpar M. 2024. Properties of the strong data processing constant for Rényi divergence. Proceedings of the 2024 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 3178–3183.","mla":"Jin, Lifu, et al. “Properties of the Strong Data Processing Constant for Rényi Divergence.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, Institute of Electrical and Electronics Engineers, 2024, pp. 3178–83, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">10.1109/ISIT57864.2024.10619367</a>.","short":"L. Jin, A.R. Esposito, M. Gastpar, in:, Proceedings of the 2024 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2024, pp. 3178–3183.","chicago":"Jin, Lifu, Amedeo Roberto Esposito, and Michael Gastpar. “Properties of the Strong Data Processing Constant for Rényi Divergence.” In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, 3178–83. Institute of Electrical and Electronics Engineers, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">https://doi.org/10.1109/ISIT57864.2024.10619367</a>."},"status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2403.10656 "}],"acknowledgement":"The work in this paper was supported in part by the Swiss National Science Foundation under Grant 200364.\r\n","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Properties of the strong data processing constant for Rényi divergence","oa":1,"conference":{"location":"Athens, Greece","end_date":"2024-07-12","name":"ISIT: International Symposium on Information Theory","start_date":"2024-07-07"},"publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory","date_created":"2024-09-08T22:01:12Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9798350382846"]},"abstract":[{"lang":"eng","text":"Strong data processing inequalities (SDPI) are an important object of study in Information Theory and have been well studied for f -divergences. Universal upper and lower bounds have been provided along with several applications, connecting them to impossibility (converse) results, concentration of measure, hypercontractivity, and so on. In this paper, we study Renyi divergence and the corresponding SDPI constant whose behavior seems to deviate from that of ordinary <1>-divergences. In particular, one can find examples showing that the universal upper bound relating its SDPI constant to the one of Total Variation does not hold in general. In this work, we prove, however, that the universal lower bound involving the SDPI constant of the Chi-square divergence does indeed hold. Furthermore, we also provide a characterization of the distribution that achieves the supremum when is equal to 2 and consequently compute the SDPI constant for Renyi divergence of the general binary channel."}],"type":"conference","date_updated":"2025-09-08T09:18:00Z"},{"date_created":"2024-09-08T22:01:12Z","publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory ","publication_identifier":{"issn":["2157-8095"],"isbn":["9798350382846"]},"abstract":[{"lang":"eng","text":"Sibson's α -mutual information has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this work, we introduce several variational representations of Sibson's α -mutual information: 1) as a supremum over joint distributions of (a combination of) KL divergences; and 2) as a supremum over functions of opportune expected values. Leveraging them, we produce a variety of novel and known results, including a generalization of transportation-cost inequalities and Fano's inequality."}],"type":"conference","date_updated":"2025-09-08T09:18:44Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Variational characterizations of Sibson's α-mutual information","conference":{"location":"Athens, Greece","end_date":"2024-07-12","name":"ISIT: International Symposium on Information Theory","start_date":"2024-07-07"},"citation":{"ieee":"A. R. Esposito, M. Gastpar, and I. Issa, “Variational characterizations of Sibson’s α-mutual information,” in <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Athens, Greece, 2024, pp. 2110–2115.","ama":"Esposito AR, Gastpar M, Issa I. Variational characterizations of Sibson’s α-mutual information. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>. Institute of Electrical and Electronics Engineers; 2024:2110-2115. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">10.1109/ISIT57864.2024.10619378</a>","apa":"Esposito, A. R., Gastpar, M., &#38; Issa, I. (2024). Variational characterizations of Sibson’s α-mutual information. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i> (pp. 2110–2115). Athens, Greece: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">https://doi.org/10.1109/ISIT57864.2024.10619378</a>","short":"A.R. Esposito, M. Gastpar, I. Issa, in:, Proceedings of the 2024 IEEE International Symposium on Information Theory , Institute of Electrical and Electronics Engineers, 2024, pp. 2110–2115.","chicago":"Esposito, Amedeo Roberto, Michael Gastpar, and Ibrahim Issa. “Variational Characterizations of Sibson’s α-Mutual Information.” In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, 2110–15. Institute of Electrical and Electronics Engineers, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">https://doi.org/10.1109/ISIT57864.2024.10619378</a>.","mla":"Esposito, Amedeo Roberto, et al. “Variational Characterizations of Sibson’s α-Mutual Information.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Institute of Electrical and Electronics Engineers, 2024, pp. 2110–15, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">10.1109/ISIT57864.2024.10619378</a>.","ista":"Esposito AR, Gastpar M, Issa I. 2024. Variational characterizations of Sibson’s α-mutual information. Proceedings of the 2024 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 2110–2115."},"status":"public","scopus_import":"1","acknowledgement":"The work in this paper was supported in part by the Swiss National Science Foundation under Grant 200364.","publication_status":"published","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT57864.2024.10619378","day":"19","month":"08","corr_author":"1","quality_controlled":"1","oa_version":"None","language":[{"iso":"eng"}],"_id":"17894","external_id":{"isi":["001304426902023"]},"isi":1,"author":[{"last_name":"Esposito","id":"9583e921-e1ad-11ec-9862-cef099626dc9","full_name":"Esposito, Amedeo Roberto","first_name":"Amedeo Roberto"},{"first_name":"Michael","last_name":"Gastpar","full_name":"Gastpar, Michael"},{"last_name":"Issa","full_name":"Issa, Ibrahim","first_name":"Ibrahim"}],"publisher":"Institute of Electrical and Electronics Engineers","year":"2024","date_published":"2024-08-19T00:00:00Z","page":"2110-2115","article_processing_charge":"No"},{"title":"Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"17895","external_id":{"isi":["001304426901091"]},"isi":1,"author":[{"first_name":"B. K.","full_name":"Dey, B. K.","last_name":"Dey"},{"first_name":"S.","last_name":"Jaggi","full_name":"Jaggi, S."},{"last_name":"Langberg","full_name":"Langberg, M.","first_name":"M."},{"last_name":"Sarwate","full_name":"Sarwate, A. D.","first_name":"A. D."},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","last_name":"Zhang"}],"conference":{"start_date":"2024-07-07","name":"ISIT: International Symposium on Information Theory","end_date":"2024-07-12","location":"Athens, Greece"},"publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory ","date_created":"2024-09-08T22:01:12Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9798350382846"]},"abstract":[{"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.","lang":"eng"}],"type":"conference","date_updated":"2025-09-08T09:19:25Z","department":[{"_id":"MaMo"}],"publication_status":"published","day":"19","doi":"10.1109/ISIT57864.2024.10619362","date_published":"2024-08-19T00:00:00Z","month":"08","page":"1586-1591","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"None","article_processing_charge":"No","citation":{"mla":"Dey, B. K., et al. “Computationally Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Institute of Electrical and Electronics Engineers, 2024, pp. 1586–91, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">10.1109/ISIT57864.2024.10619362</a>.","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.","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 <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, 1586–91. Institute of Electrical and Electronics Engineers, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">https://doi.org/10.1109/ISIT57864.2024.10619362</a>.","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.","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 <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Athens, Greece, 2024, pp. 1586–1591.","apa":"Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., &#38; Zhang, Y. (2024). Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i> (pp. 1586–1591). Athens, Greece: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">https://doi.org/10.1109/ISIT57864.2024.10619362</a>","ama":"Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>. Institute of Electrical and Electronics Engineers; 2024:1586-1591. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">10.1109/ISIT57864.2024.10619362</a>"},"status":"public","publisher":"Institute of Electrical and Electronics Engineers","year":"2024","scopus_import":"1","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. "},{"intvolume":"      2022","volume":2022,"_id":"12011","external_id":{"isi":["001254261902114"],"arxiv":["2205.06708"]},"author":[{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan"},{"first_name":"Sidharth","last_name":"Jaggi","full_name":"Jaggi, Sidharth"},{"first_name":"Michael","full_name":"Langberg, Michael","last_name":"Langberg"},{"first_name":"Anand D.","last_name":"Sarwate","full_name":"Sarwate, Anand D."}],"isi":1,"publisher":"IEEE","year":"2022","date_published":"2022-08-03T00:00:00Z","article_processing_charge":"No","page":"2523-2528","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."}],"date_created":"2022-09-04T22:02:03Z","publication":"2022 IEEE International Symposium on Information Theory","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"type":"conference","date_updated":"2025-09-10T09:40:42Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"The capacity of causal adversarial channels","conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory"},"oa":1,"status":"public","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2205.06708","open_access":"1"}],"citation":{"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.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2523–28, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">10.1109/ISIT50566.2022.9834709</a>.","short":"Y. Zhang, S. Jaggi, M. Langberg, A.D. Sarwate, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2523–2528.","chicago":"Zhang, Yihan, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. “The Capacity of Causal Adversarial Channels.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2523–28. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">https://doi.org/10.1109/ISIT50566.2022.9834709</a>.","apa":"Zhang, Y., Jaggi, S., Langberg, M., &#38; Sarwate, A. D. (2022). The capacity of causal adversarial channels. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2523–2528). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">https://doi.org/10.1109/ISIT50566.2022.9834709</a>","ama":"Zhang Y, Jaggi S, Langberg M, Sarwate AD. The capacity of causal adversarial channels. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2523-2528. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">10.1109/ISIT50566.2022.9834709</a>","ieee":"Y. Zhang, S. Jaggi, M. Langberg, and A. D. Sarwate, “The capacity of causal adversarial channels,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2523–2528."},"acknowledgement":"The work of ADS and ML was supported in part by the US National Science Foundation under awards CCF-1909468 and CCF-1909451.","scopus_import":"1","month":"08","publication_status":"published","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT50566.2022.9834709","day":"03","arxiv":1,"language":[{"iso":"eng"}],"quality_controlled":"1","oa_version":"Preprint"},{"type":"conference","date_updated":"2025-09-10T09:42:41Z","publication":"2022 IEEE International Symposium on Information Theory","date_created":"2022-09-04T22:02:04Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"abstract":[{"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).","lang":"eng"}],"oa":1,"conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory"},"title":"Heterogeneous differential privacy via graphs","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","citation":{"apa":"Torkamani, S., Ebrahimi, J. B., Sadeghi, P., D’Oliveira, R. G. L., &#38; Médard, M. (2022). Heterogeneous differential privacy via graphs. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 1623–1628). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">https://doi.org/10.1109/ISIT50566.2022.9834711</a>","ama":"Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. Heterogeneous differential privacy via graphs. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:1623-1628. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">10.1109/ISIT50566.2022.9834711</a>","ieee":"S. Torkamani, J. B. Ebrahimi, P. Sadeghi, R. G. L. D’Oliveira, and M. Médard, “Heterogeneous differential privacy via graphs,” in <i>2022 IEEE International Symposium on Information Theory</i>, 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: International Symposium on Information Theory vol. 2022, 1623–1628.","mla":"Torkamani, Sahel, et al. “Heterogeneous Differential Privacy via Graphs.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 1623–28, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">10.1109/ISIT50566.2022.9834711</a>.","chicago":"Torkamani, Sahel, Javad B. Ebrahimi, Parastoo Sadeghi, Rafael G.L. D’Oliveira, and Muriel Médard. “Heterogeneous Differential Privacy via Graphs.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:1623–28. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">https://doi.org/10.1109/ISIT50566.2022.9834711</a>.","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."},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2203.15429","open_access":"1"}],"status":"public","oa_version":"Preprint","quality_controlled":"1","language":[{"iso":"eng"}],"arxiv":1,"publication_status":"published","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT50566.2022.9834711","day":"03","month":"08","volume":2022,"intvolume":"      2022","author":[{"full_name":"Torkamani, Sahel","id":"0503e7f8-2d05-11ed-aa17-db0640c720fc","last_name":"Torkamani","first_name":"Sahel"},{"first_name":"Javad B.","last_name":"Ebrahimi","full_name":"Ebrahimi, Javad B."},{"first_name":"Parastoo","last_name":"Sadeghi","full_name":"Sadeghi, Parastoo"},{"first_name":"Rafael G.L.","full_name":"D'Oliveira, Rafael G.L.","last_name":"D'Oliveira"},{"last_name":"Médard","full_name":"Médard, Muriel","first_name":"Muriel"}],"isi":1,"external_id":{"isi":["001254261901131"],"arxiv":["2203.15429"]},"_id":"12012","year":"2022","publisher":"IEEE","page":"1623-1628","article_processing_charge":"No","date_published":"2022-08-03T00:00:00Z"},{"conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"On the capacity of additive AVCs with feedback","type":"conference","date_updated":"2025-09-10T09:42:04Z","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."}],"date_created":"2022-09-04T22:02:04Z","publication":"2022 IEEE International Symposium on Information Theory","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"language":[{"iso":"eng"}],"quality_controlled":"1","oa_version":"None","month":"08","publication_status":"published","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT50566.2022.9834850","day":"03","scopus_import":"1","status":"public","citation":{"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.","chicago":"Joshi, Pranav, Amritakshya Purkayastha, Yihan Zhang, Amitalok J. Budkuley, and Sidharth Jaggi. “On the Capacity of Additive AVCs with Feedback.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:504–9. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">https://doi.org/10.1109/ISIT50566.2022.9834850</a>.","mla":"Joshi, Pranav, et al. “On the Capacity of Additive AVCs with Feedback.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 504–09, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">10.1109/ISIT50566.2022.9834850</a>.","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.","ieee":"P. Joshi, A. Purkayastha, Y. Zhang, A. J. Budkuley, and S. Jaggi, “On the capacity of additive AVCs with feedback,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 504–509.","apa":"Joshi, P., Purkayastha, A., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S. (2022). On the capacity of additive AVCs with feedback. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 504–509). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">https://doi.org/10.1109/ISIT50566.2022.9834850</a>","ama":"Joshi P, Purkayastha A, Zhang Y, Budkuley AJ, Jaggi S. On the capacity of additive AVCs with feedback. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:504-509. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">10.1109/ISIT50566.2022.9834850</a>"},"isi":1,"author":[{"first_name":"Pranav","full_name":"Joshi, Pranav","last_name":"Joshi"},{"first_name":"Amritakshya","full_name":"Purkayastha, Amritakshya","last_name":"Purkayastha"},{"last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","orcid":"0000-0002-6465-6258","first_name":"Yihan"},{"first_name":"Amitalok J.","last_name":"Budkuley","full_name":"Budkuley, Amitalok J."},{"first_name":"Sidharth","last_name":"Jaggi","full_name":"Jaggi, Sidharth"}],"external_id":{"isi":["001254261900085"]},"_id":"12013","volume":2022,"intvolume":"      2022","article_processing_charge":"No","page":"504-509","date_published":"2022-08-03T00:00:00Z","year":"2022","publisher":"IEEE"},{"page":"2559-2564","article_processing_charge":"No","date_published":"2022-08-03T00:00:00Z","year":"2022","publisher":"IEEE","author":[{"orcid":"0000-0002-6465-6258","first_name":"Yihan","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang"},{"full_name":"Vatedka, Shashank","last_name":"Vatedka","first_name":"Shashank"}],"isi":1,"external_id":{"isi":["001254261902120"]},"_id":"12014","volume":2022,"intvolume":"      2022","oa_version":"None","language":[{"iso":"eng"}],"quality_controlled":"1","publication_status":"published","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT50566.2022.9834512","day":"03","month":"08","scopus_import":"1","citation":{"ieee":"Y. Zhang and S. Vatedka, “List-decodability of Poisson Point Processes,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2559–2564.","ama":"Zhang Y, Vatedka S. List-decodability of Poisson Point Processes. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2559-2564. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">10.1109/ISIT50566.2022.9834512</a>","apa":"Zhang, Y., &#38; Vatedka, S. (2022). List-decodability of Poisson Point Processes. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2559–2564). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">https://doi.org/10.1109/ISIT50566.2022.9834512</a>","chicago":"Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2559–64. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">https://doi.org/10.1109/ISIT50566.2022.9834512</a>.","mla":"Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2559–64, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">10.1109/ISIT50566.2022.9834512</a>.","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2559–2564.","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."},"status":"public","conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26","location":"Espoo, Finland","end_date":"2022-07-01"},"title":"List-decodability of Poisson Point Processes","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","date_updated":"2025-09-10T09:41:24Z","date_created":"2022-09-04T22:02:04Z","publication":"2022 IEEE International Symposium on Information Theory","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"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]."}]},{"date_published":"2022-08-03T00:00:00Z","article_processing_charge":"No","page":"3085-3090","publisher":"IEEE","year":"2022","external_id":{"isi":["001254261903042"]},"_id":"12015","isi":1,"author":[{"orcid":"0000-0002-6465-6258","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"}],"intvolume":"      2022","volume":2022,"month":"08","doi":"10.1109/ISIT50566.2022.9834443","day":"03","department":[{"_id":"MaMo"}],"publication_status":"published","quality_controlled":"1","oa_version":"None","language":[{"iso":"eng"}],"status":"public","citation":{"chicago":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:3085–90. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">https://doi.org/10.1109/ISIT50566.2022.9834443</a>.","mla":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 3085–90, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">10.1109/ISIT50566.2022.9834443</a>.","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 3085–3090.","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.","ieee":"Y. Zhang and S. Vatedka, “Lower bounds for multiple packing,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 3085–3090.","ama":"Zhang Y, Vatedka S. Lower bounds for multiple packing. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:3085-3090. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">10.1109/ISIT50566.2022.9834443</a>","apa":"Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds for multiple packing. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 3085–3090). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">https://doi.org/10.1109/ISIT50566.2022.9834443</a>"},"scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Lower bounds for multiple packing","conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26"},"abstract":[{"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.","lang":"eng"}],"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"publication":"2022 IEEE International Symposium on Information Theory","date_created":"2022-09-04T22:02:05Z","date_updated":"2025-09-10T09:44:24Z","type":"conference"},{"author":[{"full_name":"Fathollahi, Dorsa","last_name":"Fathollahi","first_name":"Dorsa"},{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"}],"isi":1,"_id":"12016","external_id":{"arxiv":["2201.10082"],"isi":["001254261902052"]},"volume":2022,"intvolume":"      2022","article_processing_charge":"No","page":"2154-2159","date_published":"2022-08-03T00:00:00Z","year":"2022","publisher":"IEEE","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26","location":"Espoo, Finland","end_date":"2022-07-01"},"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Polar coded computing: The role of the scaling exponent","date_updated":"2025-09-10T09:43:32Z","type":"conference","abstract":[{"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.","lang":"eng"}],"publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"publication":"2022 IEEE International Symposium on Information Theory","date_created":"2022-09-04T22:02:05Z","arxiv":1,"language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","month":"08","day":"03","doi":"10.1109/ISIT50566.2022.9834712","publication_status":"published","department":[{"_id":"MaMo"}],"scopus_import":"1","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.","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2201.10082"}],"citation":{"ista":"Fathollahi D, Mondelli M. 2022. Polar coded computing: The role of the scaling exponent. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2154–2159.","mla":"Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of the Scaling Exponent.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2154–59, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">10.1109/ISIT50566.2022.9834712</a>.","short":"D. Fathollahi, M. Mondelli, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2154–2159.","chicago":"Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of the Scaling Exponent.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2154–59. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">https://doi.org/10.1109/ISIT50566.2022.9834712</a>.","ama":"Fathollahi D, Mondelli M. Polar coded computing: The role of the scaling exponent. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2154-2159. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">10.1109/ISIT50566.2022.9834712</a>","apa":"Fathollahi, D., &#38; Mondelli, M. (2022). Polar coded computing: The role of the scaling exponent. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2154–2159). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">https://doi.org/10.1109/ISIT50566.2022.9834712</a>","ieee":"D. Fathollahi and M. Mondelli, “Polar coded computing: The role of the scaling exponent,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2154–2159."}},{"article_processing_charge":"No","page":"2535-2540","date_published":"2022-08-03T00:00:00Z","year":"2022","publisher":"Institute of Electrical and Electronics Engineers","author":[{"first_name":"Anuj Kumar","full_name":"Yadav, Anuj Kumar","last_name":"Yadav"},{"full_name":"Alimohammadi, Mohammadreza","last_name":"Alimohammadi","first_name":"Mohammadreza"},{"full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang","orcid":"0000-0002-6465-6258","first_name":"Yihan"},{"full_name":"Budkuley, Amitalok J.","last_name":"Budkuley","first_name":"Amitalok J."},{"full_name":"Jaggi, Sidharth","last_name":"Jaggi","first_name":"Sidharth"}],"isi":1,"external_id":{"isi":["001254261902116"]},"_id":"12017","volume":2022,"intvolume":"      2022","oa_version":"None","language":[{"iso":"eng"}],"quality_controlled":"1","month":"08","publication_status":"published","department":[{"_id":"MaMo"}],"day":"03","doi":"10.1109/ISIT50566.2022.9834632","scopus_import":"1","status":"public","citation":{"apa":"Yadav, A. K., Alimohammadi, M., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S. (2022). New results on AVCs with omniscient and myopic adversaries. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2535–2540). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">https://doi.org/10.1109/ISIT50566.2022.9834632</a>","ama":"Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. New results on AVCs with omniscient and myopic adversaries. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:2535-2540. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">10.1109/ISIT50566.2022.9834632</a>","ieee":"A. K. Yadav, M. Alimohammadi, Y. Zhang, A. J. Budkuley, and S. Jaggi, “New results on AVCs with omniscient and myopic adversaries,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2535–2540.","ista":"Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. 2022. New results on AVCs with omniscient and myopic adversaries. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 2535–2540.","chicago":"Yadav, Anuj Kumar, Mohammadreza Alimohammadi, Yihan Zhang, Amitalok J. Budkuley, and Sidharth Jaggi. “New Results on AVCs with Omniscient and Myopic Adversaries.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2535–40. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">https://doi.org/10.1109/ISIT50566.2022.9834632</a>.","mla":"Yadav, Anuj Kumar, et al. “New Results on AVCs with Omniscient and Myopic Adversaries.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2535–40, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">10.1109/ISIT50566.2022.9834632</a>.","short":"A.K. Yadav, M. Alimohammadi, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 2535–2540."},"conference":{"name":"ISIT: Internation Symposium on Information Theory","start_date":"2022-06-26","location":"Espoo, Finland","end_date":"2022-07-01"},"title":"New results on AVCs with omniscient and myopic adversaries","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","date_updated":"2025-09-10T09:45:03Z","abstract":[{"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.","lang":"eng"}],"date_created":"2022-09-04T22:02:06Z","publication":"2022 IEEE International Symposium on Information Theory","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]}},{"article_processing_charge":"No","page":"1324-1329","date_published":"2022-08-03T00:00:00Z","year":"2022","publisher":"Institute of Electrical and Electronics Engineers","author":[{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan"},{"first_name":"Shashank","full_name":"Vatedka, Shashank","last_name":"Vatedka"}],"isi":1,"external_id":{"isi":["001254261901080"]},"_id":"12018","volume":2022,"intvolume":"      2022","oa_version":"None","quality_controlled":"1","language":[{"iso":"eng"}],"month":"08","doi":"10.1109/ISIT50566.2022.9834815","day":"03","publication_status":"published","department":[{"_id":"MaMo"}],"scopus_import":"1","status":"public","citation":{"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.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–29, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">10.1109/ISIT50566.2022.9834815</a>.","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–1329.","chicago":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity Using Error Exponents.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:1324–29. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">https://doi.org/10.1109/ISIT50566.2022.9834815</a>.","ama":"Zhang Y, Vatedka S. Lower bounds on list decoding capacity using error exponents. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:1324-1329. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">10.1109/ISIT50566.2022.9834815</a>","apa":"Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds on list decoding capacity using error exponents. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 1324–1329). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">https://doi.org/10.1109/ISIT50566.2022.9834815</a>","ieee":"Y. Zhang and S. Vatedka, “Lower bounds on list decoding capacity using error exponents,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 1324–1329."},"conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory"},"title":"Lower bounds on list decoding capacity using error exponents","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-10T09:45:40Z","type":"conference","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."}],"publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"date_created":"2022-09-04T22:02:06Z","publication":"2022 IEEE International Symposium on Information Theory"},{"intvolume":"      2022","volume":2022,"external_id":{"isi":["001254261902119"]},"_id":"12019","isi":1,"author":[{"first_name":"Nikita","full_name":"Polyanskii, Nikita","last_name":"Polyanskii"},{"last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","orcid":"0000-0002-6465-6258","first_name":"Yihan"}],"publisher":"Institute of Electrical and Electronics Engineers","year":"2022","date_published":"2022-08-03T00:00:00Z","page":"2553-2558","article_processing_charge":"No","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"publication":"2022 IEEE International Symposium on Information Theory","date_created":"2022-09-04T22:02:07Z","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."}],"date_updated":"2025-09-10T09:46:15Z","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"List-decodable zero-rate codes for the Z-channel","conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26","location":"Espoo, Finland","end_date":"2022-07-01"},"citation":{"mla":"Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the Z-Channel.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–58, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">10.1109/ISIT50566.2022.9834829</a>.","chicago":"Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the Z-Channel.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2553–58. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">https://doi.org/10.1109/ISIT50566.2022.9834829</a>.","short":"N. Polyanskii, Y. Zhang, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 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.","ieee":"N. Polyanskii and Y. Zhang, “List-decodable zero-rate codes for the Z-channel,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2553–2558.","ama":"Polyanskii N, Zhang Y. List-decodable zero-rate codes for the Z-channel. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:2553-2558. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">10.1109/ISIT50566.2022.9834829</a>","apa":"Polyanskii, N., &#38; Zhang, Y. (2022). List-decodable zero-rate codes for the Z-channel. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2553–2558). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">https://doi.org/10.1109/ISIT50566.2022.9834829</a>"},"status":"public","scopus_import":"1","day":"03","doi":"10.1109/ISIT50566.2022.9834829","publication_status":"published","department":[{"_id":"MaMo"}],"month":"08","oa_version":"None","language":[{"iso":"eng"}],"quality_controlled":"1"},{"title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"start_date":"2021-07-12","name":"ISIT: International Symposium on Information Theory","end_date":"2021-07-20","location":"Melbourne, Australia"},"oa":1,"abstract":[{"lang":"eng","text":"This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations."}],"publication":"2021 IEEE International Symposium on Information Theory","date_created":"2021-09-27T14:33:14Z","publication_identifier":{"issn":["2157-8095"],"isbn":["978-1-5386-8210-4"],"eisbn":["978-1-5386-8209-8"]},"type":"conference","date_updated":"2025-04-15T07:50:11Z","related_material":{"record":[{"id":"10364","relation":"later_version","status":"public"}]},"month":"09","department":[{"_id":"MaMo"}],"publication_status":"published","doi":"10.1109/ISIT45174.2021.9518153","day":"01","arxiv":1,"quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.13378"}],"status":"public","citation":{"chicago":"Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” In <i>2021 IEEE International Symposium on Information Theory</i>, 2369–74. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>.","mla":"Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74, doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>.","short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, in:, 2021 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–2374.","ista":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 2369–2374.","ieee":"S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith, “Parallelism versus latency in simplified successive-cancellation decoding of polar codes,” in <i>2021 IEEE International Symposium on Information Theory</i>, Melbourne, Australia, 2021, pp. 2369–2374.","apa":"Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., &#38; Goldsmith, A. (2021). Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In <i>2021 IEEE International Symposium on Information Theory</i> (pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>","ama":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In: <i>2021 IEEE International Symposium on Information Theory</i>. Institute of Electrical and Electronics Engineers; 2021:2369-2374. doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>"},"scopus_import":"1","acknowledgement":"S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council\r\nof Canada (NSERC) and by Huawei. M. Mondelli is partially supported by the 2019 Lopez-Loreta Prize. A. Fazeli and A. Vardy were supported in part by the National Science Foundation under Grant CCF-1764104.","external_id":{"arxiv":["2012.13378"],"isi":["000701502202078"]},"_id":"10053","author":[{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"},{"first_name":"Arman","last_name":"Fazeli","full_name":"Fazeli, Arman"},{"first_name":"Alexander","last_name":"Vardy","full_name":"Vardy, Alexander"},{"last_name":"Cioffi","full_name":"Cioffi, John","first_name":"John"},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"isi":1,"date_published":"2021-09-01T00:00:00Z","article_processing_charge":"No","page":"2369-2374","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"publisher":"Institute of Electrical and Electronics Engineers","year":"2021"},{"related_material":{"record":[{"id":"9047","relation":"later_version","status":"public"}]},"month":"06","department":[{"_id":"MaMo"}],"publication_status":"published","day":"01","doi":"10.1109/ISIT44484.2020.9174141","arxiv":1,"quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1909.04892","open_access":"1"}],"citation":{"ista":"Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. 2020. Simplified successive cancellation decoding of polar codes has sublinear latency. IEEE International Symposium on Information Theory - Proceedings. ISIT: International Symposium on Information Theory vol. 2020–June, 401–406.","chicago":"Mondelli, Marco, Seyyed Ali Hashemi, John Cioffi, and Andrea Goldsmith. “Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.” In <i>IEEE International Symposium on Information Theory - Proceedings</i>, Vol. 2020–June. IEEE, 2020. <a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">https://doi.org/10.1109/ISIT44484.2020.9174141</a>.","mla":"Mondelli, Marco, et al. “Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.” <i>IEEE International Symposium on Information Theory - Proceedings</i>, vol. 2020–June, 401–406, IEEE, 2020, doi:<a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">10.1109/ISIT44484.2020.9174141</a>.","short":"M. Mondelli, S.A. Hashemi, J. Cioffi, A. Goldsmith, in:, IEEE International Symposium on Information Theory - Proceedings, IEEE, 2020.","ama":"Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. Simplified successive cancellation decoding of polar codes has sublinear latency. In: <i>IEEE International Symposium on Information Theory - Proceedings</i>. Vol 2020-June. IEEE; 2020. doi:<a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">10.1109/ISIT44484.2020.9174141</a>","apa":"Mondelli, M., Hashemi, S. A., Cioffi, J., &#38; Goldsmith, A. (2020). Simplified successive cancellation decoding of polar codes has sublinear latency. In <i>IEEE International Symposium on Information Theory - Proceedings</i> (Vol. 2020–June). Los Angeles, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">https://doi.org/10.1109/ISIT44484.2020.9174141</a>","ieee":"M. Mondelli, S. A. Hashemi, J. Cioffi, and A. Goldsmith, “Simplified successive cancellation decoding of polar codes has sublinear latency,” in <i>IEEE International Symposium on Information Theory - Proceedings</i>, Los Angeles, CA, United States, 2020, vol. 2020–June."},"acknowledgement":"M. Mondelli was partially supported by grants NSF DMS-1613091, CCF-1714305, IIS-1741162 and ONR N00014-18-1-2729. S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and by Huawei.","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Simplified successive cancellation decoding of polar codes has sublinear latency","conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2020-06-21","location":"Los Angeles, CA, United States","end_date":"2020-06-26"},"oa":1,"abstract":[{"text":"This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N 1−1/µ ), where N is the block length and µ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.","lang":"eng"}],"publication":"IEEE International Symposium on Information Theory - Proceedings","date_created":"2020-09-20T22:01:37Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9781728164328"]},"type":"conference","date_updated":"2025-09-10T10:27:05Z","date_published":"2020-06-01T00:00:00Z","article_processing_charge":"No","publisher":"IEEE","year":"2020","article_number":"401-406","external_id":{"arxiv":["1909.04892"],"isi":["000714963400069"]},"_id":"8536","author":[{"orcid":"0000-0002-3242-7020","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli"},{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"first_name":"John","full_name":"Cioffi, John","last_name":"Cioffi"},{"last_name":"Goldsmith","full_name":"Goldsmith, Andrea","first_name":"Andrea"}],"isi":1,"volume":"2020-June"}]