51 citations · 146 across the 39 of their papers we have counts for
28 papers · 1 filter
Semiquantitative Group Testing in at Most Two Rounds
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic
Semiquantitative group testing (SQGT) is a pooling method in which the test outcomes represent bounded intervals for the number of defectives. Alternatively, it may be viewed as an…
Mean-Based Trace Reconstruction over Oblivious Synchronization Channels
Mahdi Cheraghchi, Joseph Downs, João Ribeiro +1
Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that trace…
Improved algorithms for non-adaptive group testing with consecutive positives
Thach V. Bui, Mahdi Cheraghchi, An T. H. Nguyen +1
The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items whic…
Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel with Positive Dark Current
Mahdi Cheraghchi, João Ribeiro
We derive improved and easily computable upper bounds on the capacity of the discrete-time Poisson channel under an average-power constraint and an arbitrary constant dark current…
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
Mahdi Cheraghchi, Vasileios Nakos
In the long-studied problem of combinatorial group testing, one is asked to detect a set of defective items out of a population of size , using disjunctive measure…
Improved non-adaptive algorithms for threshold group testing with a gap
Thach V. Bui, Mahdi Cheraghchi, Isao Echizen
The basic goal of threshold group testing is to identify up to defective items among a population of items, where is usually much smaller than . The outcome of a tes…
An Overview of Capacity Results for Synchronization Channels
Mahdi Cheraghchi, João Ribeiro
Synchronization channels, such as the well-known deletion channel, are surprisingly harder to analyze than memoryless channels, and they are a source of many fundamental problems i…
Efficient and error-tolerant schemes for non-adaptive complex group testing and its application in complex disease genetics
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi +1
The goal of combinatorial group testing is to efficiently identify up to defective items in a large population of items, where . Defective items satisfy certain pr…
Coded trace reconstruction
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic +1
Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of \emph{coded trace reconstruction}, the design and analysi…
Improved encoding and decoding for non-adaptive threshold group testing
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi +1
The goal of threshold group testing is to identify up to defective items among a population of items, where is usually much smaller than . A test is positive if it h…
Simple Codes and Sparse Recovery with Fast Decoding
Mahdi Cheraghchi, João Ribeiro
Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. In this work, we study a very simple construction of…
A framework for generalized group testing with inhibitors and its potential application in neuroscience
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi +1
The main goal of group testing with inhibitors (GTI) is to efficiently identify a small number of defective items and inhibitor items in a large set of items. A test on a subset of…
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
Mahdi Cheraghchi, João Ribeiro
We study natural examples of binary channels with synchronization errors. These include the duplication channel, which independently outputs a given bit once or twice, and geometri…
Structural Results and Improved Upper Bounds on the Capacity of the Discrete-Time Poisson Channel
Mahdi Cheraghchi, João Ribeiro
New capacity upper bounds are presented for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a simple consequence of techniq…
Efficiently Decodable Non-Adaptive Threshold Group Testing
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi +1
We consider non-adaptive threshold group testing for identification of up to defective items in a set of items, where a test is positive if it contains at least $2 \leq u \…
Capacity Upper Bounds for Deletion-Type Channels
Mahdi Cheraghchi
We develop a systematic approach, based on convex programming and real analysis, for obtaining upper bounds on the capacity of the binary deletion channel and, more generally, chan…
Expressions for the Entropy of Binomial-Type Distributions
Mahdi Cheraghchi
We develop a general method for computing logarithmic and log-gamma expectations of distributions. As a result, we derive series expansions and integral representations of the entr…
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
Mahdi Cheraghchi, Piotr Indyk
For every fixed constant , we design an algorithm for computing the -sparse Walsh-Hadamard transform of an -dimensional vector in time $k^{1+α} (\l…
Capacity of Non-Malleable Codes
Mahdi Cheraghchi, Venkatesan Guruswami
Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages in a manner so that tampering the codeword causes the decoder to either output $s…
Non-Malleable Coding Against Bit-wise and Split-State Tampering
Mahdi Cheraghchi, Venkatesan Guruswami
Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error…
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
We prove that a random linear code over F_q, with probability arbitrarily close to 1, is list decodable at radius (1-1/q-ε) with list size L=O(1/ε^2) and rate R=Ω_q(ε^2/(log^3(1/ε)…
Coding-Theoretic Methods for Sparse Recovery
Mahdi Cheraghchi
We review connections between coding-theoretic objects and sparse learning problems. In particular, we show how seemingly different combinatorial objects such as error-correcting c…
Derandomization and Group Testing
Mahdi Cheraghchi
The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial i…
Group Testing with Probabilistic Tests: Theory, Design and Application
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi +1
Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items…