Publications de 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