Aslan Tchamkerten
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Aslan Tchamkerten has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Shashank Vatedka
Department of Electrical Engineering, Indian Institute of Technology Hyderabad, Hyderabad, India
5 shared publications Venkat Chandar
DE Shaw
5 shared publications- Venkat Chandar
Research Laboratory of Electronics Massachusetts Institute of Technology. He
4 shared publications David Tse
Department of Electrical Engineering Stanford University Stanford California USA
3 shared publications- Marat V. Burnashev
Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia
3 shared publications Ehsan Ebrahimzadeh
Department of Electrical Engineering UCLA Los Angeles California USA
2 shared publications
Latest Publications
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 8069-8086
Compression With Privacy-Preserving Random Access
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 8069-8086
Compression With Privacy-Preserving Random Access
- 1 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (10) , 6823-6833
Feedback Increases the Capacity of Queues With Bounded Service Times
- 1 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (10) , 6823-6833
Feedback Increases the Capacity of Queues With Bounded Service Times
- 2 February 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 3 (4) , 711-719
Local Decoding in Distributed Compression
A recent result says that the lossless compression of a single source Xn is achievable with a strong locality property; any Xi can be decoded from a constant number of compressed bits, with a vanishing in n probability of error. By contrast, we show that for two separately encoded sources pXn, Y nq, lossless compression and strong locality is generally not possible. Specifically, we show that for the class of “confusable” sources, strong locality cannot be achieved whenever one of the sources is compressed below its entropy. Irrespective of n, there always exists at least one index i for which the probability of incorrectly decoding pXi, Yiq is lower bounded by 2’Opdq, where d denotes the worst-case (over indices) number of compressed bits accessed by the local decoder. Conversely, if the source is not confusable, strong locality is possible even if one of the sources is compressed below its entropy. Results extend to an arbitrary number of sources.
- 2 February 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 3 (4) , 711-719
Local Decoding in Distributed Compression
A recent result says that the lossless compression of a single source Xn is achievable with a strong locality property; any Xi can be decoded from a constant number of compressed bits, with a vanishing in n probability of error. By contrast, we show that for two separately encoded sources pXn, Y nq, lossless compression and strong locality is generally not possible. Specifically, we show that for the class of “confusable” sources, strong locality cannot be achieved whenever one of the sources is compressed below its entropy. Irrespective of n, there always exists at least one index i for which the probability of incorrectly decoding pXi, Yiq is lower bounded by 2’Opdq, where d denotes the worst-case (over indices) number of compressed bits accessed by the local decoder. Conversely, if the source is not confusable, strong locality is possible even if one of the sources is compressed below its entropy. Results extend to an arbitrary number of sources.
- Open Access
Local Decoding in Distributed Compression
It was recently shown that the lossless compression of a single source $X^n$ is achievable with a notion of strong locality; any $X_i$ can be decoded from a constant number of compressed bits, with a vanishing in $n$ probability of error. By contrast, we show that for two separately encoded sources $(X^n,Y^n)$, lossless compression and strong locality is generally not possible. Specifically, we show that for the class of ``confusable'' sources, strong locality cannot be achieved whenever one of the sources is compressed below its entropy. Irrespective of $n$, for some index $i$ the probability of error of decoding $(X_i,Y_i)$ is lower bounded by $2^{-O(d)}$, where $d$ denotes the number of compressed bits accessed by the local decoder. Conversely, if the source is not confusable, strong locality is possible even if one of the sources is compressed below its entropy. Results extend to an arbitrary number of sources.Open AccessLocal Decoding in Distributed Compression
It was recently shown that the lossless compression of a single source $X^n$ is achievable with a notion of strong locality; any $X_i$ can be decoded from a constant number of compressed bits, with a vanishing in $n$ probability of error. By contrast, we show that for two separately encoded sources $(X^n,Y^n)$, lossless compression and strong locality is generally not possible. Specifically, we show that for the class of ``confusable'' sources, strong locality cannot be achieved whenever one of the sources is compressed below its entropy. Irrespective of $n$, for some index $i$ the probability of error of decoding $(X_i,Y_i)$ is lower bounded by $2^{-O(d)}$, where $d$ denotes the number of compressed bits accessed by the local decoder. Conversely, if the source is not confusable, strong locality is possible even if one of the sources is compressed below its entropy. Results extend to an arbitrary number of sources. - 4 July 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (11) , 7396-7409
Error-Correction for Sparse Support Recovery Algorithms
Consider the compressed sensing setup where the support s* of an m-sparse d-dimensional signal x is to be recovered from n linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate sin of the true support s*, and outputs a refined support estimate sout. We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is sout ⊇ s*. These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in m number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is O(mnd). Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE’s support recovery performance lies between OMP and BP. These results show that LiRE can be used generically, on top of any suboptimal baseline support recovery algorithm, to improve support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Alternatively, LiRE may be used as a standalone support recovery algorithm that is competitive with respect to OMP.
- 4 July 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (11) , 7396-7409
Error-Correction for Sparse Support Recovery Algorithms
Consider the compressed sensing setup where the support s* of an m-sparse d-dimensional signal x is to be recovered from n linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate sin of the true support s*, and outputs a refined support estimate sout. We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is sout ⊇ s*. These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in m number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is O(mnd). Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE’s support recovery performance lies between OMP and BP. These results show that LiRE can be used generically, on top of any suboptimal baseline support recovery algorithm, to improve support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Alternatively, LiRE may be used as a standalone support recovery algorithm that is competitive with respect to OMP.
- 7 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (9) , 5840-5852
Capacity-Achieving Input Distribution in Per-Sample Zero-Dispersion Model of Optical Fiber
The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint.
- 7 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (9) , 5840-5852
Capacity-Achieving Input Distribution in Per-Sample Zero-Dispersion Model of Optical Fiber
The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint.
- 11 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (9) , 5790-5805
Local Decode and Update for Big Data Compression
This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength.
- 11 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (9) , 5790-5805
Local Decode and Update for Big Data Compression
This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength.
- 30 January 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (6) , 3317-3326
Bits Through Queues With Feedback
In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times.
- 30 January 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (6) , 3317-3326
Bits Through Queues With Feedback
In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times.
- 1 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 572-576
Local Decoding and Update of Compressed Data
In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.
- 1 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 572-576
Local Decoding and Update of Compressed Data
In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.
- Open Access
Somatic mutations render human exome and pathogen DNA more similar
Immunotherapy has recently shown important clinical successes in a substantial number of oncology indications. Additionally, the tumor somatic mutation load has been shown to associate with response to these therapeutic agents, and specific mutational signatures are hypothesized to improve this association, including signatures related to pathogen insults. We sought to study in silico the validity of these observations and how they relate to each other. We first addressed whether somatic mutations typically involved in cancer may increase, in a statistically meaningful manner, the similarity between common pathogens and the human exome. Our study shows that common mutagenic processes increase, in the upper range of biologically plausible frequencies, the similarity between cancer exomes and pathogen DNA at a scale of 12-16 nucleotide sequences and established that this increased similarity is due to the specific mutation distribution of the considered mutagenic processes. Next, we studied the impact of mutation rate and showed that increasing mutation rate generally results in an increased similarity between the cancer exome and pathogen DNA, at a scale of 4-5 amino acids. Finally, we investigated whether the considered mutational processes result in amino-acid changes with functional relevance that are more likely to be immunogenic. We showed that functional tolerance to mutagenic processes across species generally suggests more resilience to mutagenic processes that are due to exposure to elements of nature than to mutagenic processes that are due to exposure to cancer-causing artificial substances. These results support the idea that recognition of pathogen sequences as well as differential functional tolerance to mutagenic processes may play an important role in the immune recognition process involved in tumor infiltration by lymphocytes.
Open AccessSomatic mutations render human exome and pathogen DNA more similar
Immunotherapy has recently shown important clinical successes in a substantial number of oncology indications. Additionally, the tumor somatic mutation load has been shown to associate with response to these therapeutic agents, and specific mutational signatures are hypothesized to improve this association, including signatures related to pathogen insults. We sought to study in silico the validity of these observations and how they relate to each other. We first addressed whether somatic mutations typically involved in cancer may increase, in a statistically meaningful manner, the similarity between common pathogens and the human exome. Our study shows that common mutagenic processes increase, in the upper range of biologically plausible frequencies, the similarity between cancer exomes and pathogen DNA at a scale of 12-16 nucleotide sequences and established that this increased similarity is due to the specific mutation distribution of the considered mutagenic processes. Next, we studied the impact of mutation rate and showed that increasing mutation rate generally results in an increased similarity between the cancer exome and pathogen DNA, at a scale of 4-5 amino acids. Finally, we investigated whether the considered mutational processes result in amino-acid changes with functional relevance that are more likely to be immunogenic. We showed that functional tolerance to mutagenic processes across species generally suggests more resilience to mutagenic processes that are due to exposure to elements of nature than to mutagenic processes that are due to exposure to cancer-causing artificial substances. These results support the idea that recognition of pathogen sequences as well as differential functional tolerance to mutagenic processes may play an important role in the immune recognition process involved in tumor infiltration by lymphocytes.