ATAslan Tchamkerten

Aslan Tchamkerten

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Local Decoding in Distributed Compression

    by Shashank Vatedka, Venkat Chandar, Aslan Tchamkerten

    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

    by Shashank Vatedka, Venkat Chandar, Aslan Tchamkerten

    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.

  • Error-Correction for Sparse Support Recovery Algorithms

    by Mohammad Mehrabi, Aslan Tchamkerten

    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.


  • Capacity-Achieving Input Distribution in Per-Sample Zero-Dispersion Model of Optical Fiber

    by Jihad Fahs, Aslan Tchamkerten, Mansoor I. Yousefi

    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.


  • Local Decode and Update for Big Data Compression

    by Shashank Vatedka, Aslan Tchamkerten

    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.


  • Bits Through Queues With Feedback

    by Laure Aptel, Aslan Tchamkerten

    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.


  • Local Decoding and Update of Compressed Data

    by Shashank Vatedka, Aslan Tchamkerten

    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

    by Ehsan Ebrahimzadeh, Maggie Engler, David Tse, Razvan Cristescu, Aslan Tchamkerten

    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.