Publications by Mahdi Cheraghchi Bashi Astaneh

Noise-Resilient Group Testing: Limitations and Constructions

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

Springer2009

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

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

Noise-Resilient Group Testing: Limitations and Constructions

Invertible Extractors and Wiretap Protocols

Computational Hardness and Explicit Constructions of Error Correcting Codes

On Matrix Rigidity and the Complexity of Linear Forms

On Matrix Rigidity and the Complexity of Linear Forms

Invertible Extractors and Wiretap Protocols

Noise-Resilient Group Testing: Limitations and Constructions

Computational Hardness and Explicit Constructions of Error Correcting Codes