Imperial College London

Dr Mahdi Cheraghchi

Faculty of EngineeringDepartment of Computing




+44 (0)20 7594 9043m.cheraghchi Website CV




Mr Jamie Perrins +44 (0)20 7594 3148




353ACE ExtensionSouth Kensington Campus





I'm a Lecturer (Assistant Professor) in the Department of Computing. Previously, I have been a Qualcomm Research Fellowat the Simons Institute for the Theory of Computing of U.C. Berkeley and have held post-doctoral researcher positions at the MIT Computer Science and Artificial Intelligence Lab (hosted by Piotr Indyk), Computer Science Department of the Carnegie Mellon University (hosted by Venkat Guruswami) and the University of Texas at Austin (hosted by David Zuckerman).

Research interests

I'm mainly interested in Theoretical Computer Science, or more specifically:

  • Interconnections between electrical engineering and theoretical computer science (particularly coding and information theory and signal processing),
  • Sparse recovery (e.g., compressive sensing and combinatorial group testing) and high-dimensional geometry,
  • Information-theoretic privacy and security,
  • The use of randomness in computation, and how to do things equally well without using randomness,
  • Approximation algorithms and hardness of approximation.




Cheraghchi M, Ribeiro J, 2018, Improved Capacity Upper Bounds for the Discrete-Time Poisson Channel., Corr, Vol:abs/1801.02745

Bui TV, Kuribayashi M, Cheraghchi M, et al., 2017, Efficiently Decodable Non-Adaptive Threshold Group Testing., Corr, Vol:abs/1712.07509

Lin F, Safavi-Naini R, Cheraghchi M, et al., 2017, Non-Malleable Codes with Leakage and Applications to Secure Communication., Corr, Vol:abs/1708.05462

Cheraghchi M, 2017, Expressions for the entropy of binomial-type distributions., Corr, Vol:abs/1708.06394


Cheraghchi Bashi Astaneh M, Capacity upper bounds for deletion-type channels, Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, ISSN:0737-8017

More Publications