About This Site
cheraghchi.info is the research home of Mahdi Cheraghchi, a theoretical computer scientist whose work addresses fundamental questions about how information can be stored, transmitted, protected, and recovered reliably and efficiently. This site publishes his research papers, preprints, manuscripts, and technical writings.
Research Focus
The research published here sits at the boundary of theoretical computer science, coding theory, information theory, and cryptography. The central questions driving this work are mathematical in nature: what are the fundamental limits of reliable communication over noisy channels? How much information can be protected against adversarial tampering? How can high-dimensional sparse signals be recovered from few measurements? How does randomness help — or hinder — efficient computation?
These questions matter both as deep mathematical problems and as foundations for practical systems in data storage, communications, privacy, and security.
Core Research Areas
Coding and information theory. This work studies the capacity of communication channels — particularly deletion-type channels, which model errors where bits are inserted or dropped rather than flipped. A major result establishes tight capacity upper bounds for deletion channels, resolving longstanding open questions in the field. Related work characterises the capacity of non-malleable codes, a class of codes designed to protect data against adversarial tampering.
Non-malleable codes and cryptographic security. A sustained line of research develops the theory of non-malleable codes — encoding schemes that guarantee, even when an adversary corrupts the codeword arbitrarily, that the decoded output is either correct or completely unrelated to the original message. This work establishes capacity results and constructions for both bit-wise and split-state tampering models, with direct implications for tamper-resilient cryptography.
Sparse recovery and compressive sensing. This research asks how a sparse signal — one with few non-zero components — can be reconstructed efficiently from a small number of linear measurements. A key contribution is a nearly optimal deterministic algorithm for the Sparse Walsh-Hadamard Transform, giving the first sub-linear deterministic algorithm of its kind. Related work studies restricted isometry properties of Fourier matrices and their consequences for list decoding of random linear codes.
Randomness in computation and derandomisation. A recurring theme across multiple research threads is the role of randomness: understanding when randomness is necessary, when it can be eliminated, and how to replace randomised algorithms with equally efficient deterministic ones.
Approximation algorithms and computational hardness. This line of work studies which optimisation problems can be solved approximately in polynomial time and which cannot, contributing to the theory of hardness of approximation.
Selected Publications
- Mahdi Cheraghchi. Capacity Upper Bounds for Deletion-Type Channels. Journal of the ACM (JACM), 66(2)9, 2019. Extended abstract at STOC 2018.
- Mahdi Cheraghchi, Piotr Indyk. Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform. ACM Transactions on Algorithms (TALG), 13(3), pp. 1–36, 2017. Extended abstract at SODA 2016.
- Mahdi Cheraghchi, Venkatesan Guruswami. Capacity of Non-Malleable Codes. IEEE Transactions on Information Theory, 62(3), pp. 1097–1118, 2016. Extended abstract at ITCS 2014.
- Mahdi Cheraghchi, Venkatesan Guruswami. Non-Malleable Coding Against Bit-wise and Split-State Tampering. Journal of Cryptology, 30(1), pp. 191–241, 2015. Extended abstract at TCC 2014.
- Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker. Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SIAM Journal on Computing (SICOMP), 42(5), pp. 1888–1914, 2013. Extended abstract at SODA 2013.
- Full list of publications: cheraghchi.info/publications
- Google Scholar: scholar.google.com/citations?user=pDkhB5EAAAAJ
- Total citations: 1,584 · h-index: 21 · i10-index: 36
Disclaimer:
Mahdi Cheraghchi’s personal academic website is called Cheraghchi.info. This website’s content, including research papers, preprints, manuscripts, technical writings, opinions, and commentary, is entirely his own. The National Science Foundation, Imperial College London, the University of Michigan, and any other organization, employer, funder, or affiliated group do not endorse, support, or hold any official position on this website.
Academic Content and Research
This website makes research papers, preprints, and manuscripts accessible for scholarly and instructional purposes. Research findings are subject to revision, correction, and peer review even though every attempt is made to ensure accuracy. The final published versions of preprints and manuscripts may be different from those posted here. For reference and citation purposes, readers should refer to the official published versions. A paper is not endorsed by any journal, conference, or publisher just because it appears on this website.
No Expert Guidance
This website does not provide any legal, financial, investment, medical, or other professional advice. Applications in communications, cryptography, data security, and computer systems are the subject of theoretical and scholarly research discussions. They shouldn’t be used as a guide when making operational, financial, or commercial decisions. A qualified professional should be consulted by readers who need professional advice.
Disclosure of Finances
Under grants NSF CCF-2107345 and NSF CCF-2006455, the US National Science Foundation provided partial funding for research carried out and published through this website. This funding does not constitute a financial stake in any commercial product, business, or technology; rather, it solely supports academic research activities.
This website doesn’t accept sponsored content, run advertisements, or get paid for highlighting, endorsing, or linking to any goods, services, or businesses. Any external links are not endorsements or commercial relationships; they are only included for academic reference and convenience.
Any business or product that may be discussed or cited in research published on this website has no financial stake in the author and is not compensated by them. Any significant changes to this will be made publicly known.
External Links
Links to third-party websites, such as academic databases, publishers, and institutional pages, may be found on this website. Cheraghchi.info has no control over the content, accuracy, or privacy practices of external websites and takes no responsibility for them; these links are merely for reference.
Intellectual Property
Unless otherwise noted, all original content on this website, including writings, descriptions, and site structure, belongs to Mahdi Cheraghchi. Co-authored research papers are the collective intellectual property of all listed authors. The respective journals or publishers may own the copyright to published papers; readers should refer to the specific publication pages for licensing terms.
Institutional Affiliation
The research on this site is conducted at the EECS Department, University of Michigan, Ann Arbor. Prior research was carried out at Imperial College London, the Simons Institute for the Theory of Computing (UC Berkeley), MIT CSAIL, Carnegie Mellon University, and the University of Texas at Austin.
Contact and Profiles
Email: mahdich@umich.edu
ORCID: 0000-0001-8957-0306
Scopus Author ID: 35112994100
ResearcherID: N-1367-2015