Publications by Mahdi Cheraghchi Bashi Astaneh

Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Martin Vetterli, Amin Karbasi, Ali Hormati, Mahdi Cheraghchi Bashi Astaneh

Detection of defective members of large populations has been widely studied in the statistics community under the name ``group testing'', a problem which dates back to World War~II when it was suggested for syphilis screening. There the main interest is to ...

2009

Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

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 polynom ...

2009

Bit Precision Analysis for Compressed Sensing

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

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 ac ...

2009

Invertible Extractors and Wiretap Protocols

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the messa ...

2009

Computational Hardness and Explicit Constructions of Error Correcting Codes

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

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

, constru ...

2006

Locally Testable Codes

Mahdi Cheraghchi Bashi Astaneh

Error correcting codes are combinatorial objects that allow reliable recovery of information in presence of errors by cleverly augmenting the original information with a certain amount of redundancy. The availability of efficient means of error detection i ...

2005

On Matrix Rigidity and the Complexity of Linear Forms

Mahdi Cheraghchi Bashi Astaneh

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontri ...

2005

Mahdi Cheraghchi Bashi Astaneh

Graph Chatbot

Chat with Graph Search

Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Bit Precision Analysis for Compressed Sensing

Invertible Extractors and Wiretap Protocols

Computational Hardness and Explicit Constructions of Error Correcting Codes

Locally Testable Codes

On Matrix Rigidity and the Complexity of Linear Forms

Bit Precision Analysis for Compressed Sensing

Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Invertible Extractors and Wiretap Protocols

Computational Hardness and Explicit Constructions of Error Correcting Codes

Locally Testable Codes

On Matrix Rigidity and the Complexity of Linear Forms