Publications
76 results found
Cheraghchi M, Hastad J, Isaksson M, et al., 2010, Approximating Linear Threshold Predicates, 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010), Publisher: SPRINGER-VERLAG BERLIN, Pages: 110-+, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 3
Cheraghchi M, 2010, Improved Constructions for Non-adaptive Threshold Group Testing., Publisher: Springer, Pages: 552-564
Cheraghchi M, Karbasi A, Mohajer S, et al., 2010, Graph-Constrained Group Testing, CoRR, Vol: abs/1001.1445
Cheraghchi M, 2010, Improved Constructions for Non-adaptive Threshold Group Testing, AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, Vol: 6198, Pages: 552-564, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 6
Cheraghchi M, Håstad J, Isaksson M, et al., 2010, Approximating Linear Threshold Predicates., Electron. Colloquium Comput. Complex., Vol: TR10
Cheraghchi M, Shokrollahi AN, 2009, Almost-uniform sampling of points on high-dimensional algebraic varieties, 26th International Symposium on Theoretical Aspects of Computer Science, Pages: 277-288, ISSN: 1868-8969
We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant. © M. Cheraghchi and A. Shokrollahi.
Cheraghchi M, 2009, Noise-resilient group testing: limitations and constructions, 17th International Symposium on Fundamentals of Computation Theory, Publisher: Springer VERLAG, Pages: 62-73, ISSN: 0302-9743
We study combinatorial group testing schemes for learning d-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise-resilient scheme in this model can only approximately reconstruct the sparse vector. On the positive side, we give a general framework for construction of highly noise-resilient group testing schemes using randomness condensers. Simple randomized instantiations of this construction give non-adaptive measurement schemes, with m = O(d logn) measurements, that allow efficient reconstruction of d-sparse vectors up to O(d) false positives even in the presence of δm false positives and Ω(m/d) false negatives within the measurement outcomes, for any constant δ< 1. None of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit (and incomparable) constructions, in particular one matching the randomized trade-off but using m = O(d 1 + o(1) logn) measurements. We also obtain explicit constructions that allow fast reconstruction in time poly(m), which would be sublinear in n for sufficiently sparse vectors.
Ardestanizadeh E, Cheraghchi M, Shokrollahi A, 2009, Bit precision analysis for compressed sensing, IEEE International Symposium on Information Theory (ISIT 2009), Publisher: IEEE, ISSN: 2157-8095
This paper studies the stability of some reconstruction algorithms for compressed sensing in terms of the bit precision. Considering the fact that practical digital systems deal with discretized signals, we motivate the importance of the total number of accurate bits needed from the measurement outcomes in addition to the number of measurements. It is shown that if one uses a 2 k times n Vandermonde matrix with roots on the unit circle as the measurement matrix, O(lscr + k log n/k) bits of precision per measurement are sufficient to reconstruct a k-sparse signal x isin Ropfn with dynamic range (i.e., the absolute ratio between the largest and the smallest nonzero coefficients) at most 2lscr within lscr bits of precision, hence identifying its correct support. Finally, we obtain an upper bound on the total number of required bits when the measurement matrix satisfies a restricted isometry property, which is in particular the case for random Fourier and Gaussian matrices. For very sparse signals, the upper bound on the number of required bits for Vandermonde matrices is shown to be better than this general upper bound.
Cheraghchi M, 2009, Capacity achieving codes from randomness conductors, IEEE International Symposium on Information Theory (ISIT 2009), Publisher: IEEE, Pages: 2639-2643, ISSN: 2157-8095
We give a general framework for construction of small ensembles of capacity achieving linear codes for a wide range of (not necessarily memoryless) discrete symmetric channels, and in particular, the binary erasure and symmetric channels. The main tool used in our constructions is the notion of randomness extractors and lossless condensers that are regarded as central tools in theoretical computer science. Same as random codes, the resulting ensembles preserve their capacity achieving properties under any change of basis. Our methods can potentially lead to polynomial-sized ensembles; however, using known explicit constructions of randomness conductors we obtain specific ensembles whose size is as small as quasipolynomial in the block length. By applying our construction to Justesen's concatenation scheme (Justesen, 1972) we obtain explicit capacity achieving codes for BEC (resp., BSC) with almost linear time encoding and almost linear time (resp., quadratic time) decoding and exponentially small error probability. The explicit code for BEC is defined and capacity achieving for every block length.
Cheraghchi M, 2009, Capacity achieving codes From randomness conductors., Publisher: IEEE, Pages: 2639-2643
Ardestanizadeh E, Cheraghchi M, Shokrollahi A, 2009, Bit precision analysis for compressed sensing., Publisher: IEEE, Pages: 1-5
Cheraghchi M, Shokrollahi A, 2009, Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties, CoRR, Vol: abs/0902.1254
Cheraghchi M, Didier F, Shokrollahi A, 2009, Invertible extractors and wiretap protocols., Publisher: IEEE, Pages: 1934-1938
Cheraghchi M, Didier F, Shokrollahi A, 2009, Invertible Extractors and Wiretap Protocols, 2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4, Pages: 1934-1938
- Author Web Link
- Cite
- Citations: 3
Cheraghchi M, Shokrollahi A, Wigderson A, 2006, Computational hardness and explicit constructions of error correcting codes, Pages: 1173-1179
We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers n and k, constructs polynomially many linear codes of block length n and dimension k, most of which achieving the Gilbert-Varshamov bound. The success of the procedure relies on the assumption that the exponential time class of E def = DTIME[2<sup>O(n)</sup>] is not contained in the sub-exponential space class DSPACE[2<sup>o(n)</sup>]. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail.
Cheraghchi M, 2005, On Matrix Rigidity and the Complexity of Linear Forms, Electron. Colloquium Comput. Complex., Vol: TR05
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.