Mahdi Cheraghchi

STOC Conference 2023 Conference Paper

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms

• Huck Bennett
• Mahdi Cheraghchi
• Venkatesan Guruswami
• João Ribeiro 0002

FOCS Conference 2020 Conference Paper

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 k defective items out of a population of size n, using m ≪ n disjunctive measurements. In the non-adaptive setting, the most widely used combinatorial objects are disjunct and list-disjunct matrices, which define incidence matrices of test schemes. Disjunct matrices allow the identification of the exact set of defectives, whereas list disjunct matrices identify a small superset of the defectives. Apart from the combinatorial guarantees, it is often of key interest to equip measurement designs with efficient decoding algorithms. The most efficient decoders should run in sublinear time in n, and ideally near-linear in the number of measurements m. In this work, we give several constructions with an optimal number of measurements and near-optimal decoding time for the most fundamental group testing tasks, as well as for central tasks in the compressed sensing and heavy hitters literature. For many of those tasks, the previous measurement-optimal constructions needed time either quadratic in the number of measurements or linear in the universe size. Among our results are the following: a construction of disjunct matrices matching the best-known construction in terms of the number of rows m, but achieving nearly linear decoding time in m; a construction of list disjunct matrices with the optimal m=O(klog(n/k) number of rows and nearly linear decoding time in m; error-tolerant variations of the above constructions; a non-adaptive group testing scheme for the “for-each” model with m=O(klogn) measurements and O(m) decoding time; a streaming algorithm for the “for-all” version of the heavy hitters problem in the strict turnstile model with near-optimal query time, as well as a “list decoding” variant obtaining also near-optimal update time and O(klog(n/k)) space usage; an l2/l2 weak identification system for compressed sensing with nearly optimal sample complexity and nearly linear decoding time in the sketch length. Most of our results are obtained via a clean and novel approach that avoids list-recoverable codes or related complex techniques that were present in almost every state-of-the-art work on efficiently decodable constructions of such objects.

STOC Conference 2018 Conference Paper

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, channels with i.i.d. insertions and deletions. Other than the classical deletion channel, we give a special attention to the Poisson-repeat channel introduced by Mitzenmacher and Drinea (IEEE Transactions on Information Theory, 2006). Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions). Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate, real-valued, and often concave function over a bounded interval. The corresponding univariate function is carefully designed according to the underlying distribution of repetitions and the choices vary depending on the desired strength of the upper bounds as well as the desired simplicity of the function (e.g., being only efficiently computable versus having an explicit closed-form expression in terms of elementary, or common special, functions). Among our results, we show that the capacity of the binary deletion channel with deletion probability d is at most (1− d ) logϕ for d ≥ 1/2, and, assuming the capacity function is convex, is at most 1− d log(4/ϕ) for d <1/2, where ϕ=(1+√5)/2 is the golden ratio. This is the first nontrivial capacity upper bound for any value of d outside the limiting case d → 0 that is fully explicit and proved without computer assistance. Furthermore, we derive the first set of capacity upper bounds for the Poisson-repeat channel. Our results uncover further striking connections between this channel and the deletion channel, and suggest, somewhat counter-intuitively, that the Poisson-repeat channel is actually analytically simpler than the deletion channel and may be of key importance to a complete understanding of the deletion channel. Finally, we derive several novel upper bounds on the capacity of the deletion channel. All upper bounds are maximums of efficiently computable, and concave, univariate real functions over a bounded domain. In turn, we upper bound these functions in terms of explicit elementary and standard special functions, whose maximums can be found even more efficiently (and sometimes, analytically, for example for d =1/2). Along the way, we develop several new techniques of potentially independent interest. For example, we develop systematic techniques to study channels with mean constraints over the reals. Furthermore, we motivate the study of novel probability distributions over non-negative integers, as well as novel special functions which could be of interest to mathematical analysis.

SODA Conference 2016 Conference Paper

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

• Mahdi Cheraghchi
• Piotr Indyk

SODA Conference 2013 Conference Paper

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/∊))). Up to the polylogarithmic factor in 1/∊ and constant factors depending on q, this matches the lower bound L = Ω q (1/∊ 2 ) for the list size and upper bound R = O q (∊ 2 ) for the rate. Previously only existence (and not abundance) of such codes was known for the special case q = 2 (Guruswami, Håstad, Sudan and Zuckerman, 2002). In order to obtain our result, we employ a relaxed version of the well known Johnson bound on list decoding that translates the average Hamming distance between codewords to list decoding guarantees. We furthermore prove that the desired average-distance guarantees hold for a code provided that a natural complex matrix encoding the codewords satisfies the Restricted Isometry Property with respect to the Euclidean norm (RIP-2). For the case of random binary linear codes, this matrix coincides with a random submatrix of the Hadamard-Walsh transform matrix that is well studied in the compressed sensing literature. Finally, we improve the analysis of Rudelson and Vershynin (2008) on the number of random frequency samples required for exact reconstruction of k -sparse signals of length N. Specifically, we improve the number of samples from O ( k log( N ) log 2 ( k )(log k + log log N )) to O ( k log( N ) log 3 ( k )). The proof involves bounding the expected supremum of a related Gaussian process by using an improved analysis of the metric defined by the process. This improvement is crucial for our application in list decoding.

SODA Conference 2012 Conference Paper

Submodular functions are noise stable

• Mahdi Cheraghchi
• Adam R. Klivans
• Pravesh K. Kothari
• Homin K. Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on {−1, 1} n (for any constant accuracy parameter ∊). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular functions required either query access or strong assumptions about the types of submodular functions to be learned (and did not hold in the agnostic setting). Additionally we give simple algorithms that efficiently release differentially private answers to all Boolean conjunctions and to all halfspaces with constant average error, subsuming and improving recent work due to Gupta, Hardt, Roth and Ullman (STOC 2011).