Home Page of Mahdi Cheraghchi

Mahdi Cheraghchi
he/him/his

pronounced as "MA-hdee che-RUG-chee"
(IPA: /'mæhdiː t͡ʃɛ'ɹɑːɣt͡ʃ'iː/)

Snail mail:
2260 Hayward St., Room 3603
Department of EECS
University of Michigan
Ann Arbor, MI 48109
USA

Phone: +1 (734) 763-9165
Fax: +1 (734) 763-1260
Email:

Call for Papers: With Robert Calderbank, Krishna Narayanan, Henry Pfister, and Mary Wootters, I'm editing a special issue of the IEEE BITS magazine on Error-Correcting Codes and invite expository/tutorial articles. Submission deadline: April 17, 2025 for a White Paper, followed by June 20, 2025 for the Full Manuscript. Feel free to contact any of us for any questions or to discuss a potential submission.

I'm an Associate Professor of Computer Science and Engineering at the EECS Department of the University of Michigan, Ann Arbor. Previously, I have been on the faculty of the Department of Computing, Imperial College London (where I maintain an Honorary Senior Lecturer position), a Qualcomm Research Fellow at the Simons Institute for the Theory of Computing of U.C. Berkeley and post-doctoral scholar at the MIT Computer Science and Artificial Intelligence Lab (hosted by Piotr Indyk), Computer Science Department of the Carnegie Mellon University (hosted by Venkatesan Guruswami) and the University of Texas at Austin (hosted by David Zuckerman).

Prospective students: Our CS Theory lab is always looking for motivated Ph.D. students with strong math background. If you are a prospective student interested in theoretical computer science, information and coding theory, privacy or related subjects (see my interests below), please contact me and describe your background and goals. Apply to our graduate program here, and mention my name as your potential advisor in your application. We don't require GRE scores and accept several English language proficiency tests (TOEFL, IELTS, and more).

Application fee waivers: I stand against application fees. I'm especially disappointed by the fact that nearly all US schools do not provide any application fee waivers for international students, which I see as a form of discrimination and I will continue to work against such policies. Until that changes, if you are a qualified international Ph.D. applicant applying to join the CS Theory lab and are unable to pay the application fee, please contact me. Like past years, I hope to be able to help a limited number of qualified applicants by paying their application fees.

Post-doc positions: While I personally don't currently have funding for a new postdoc at the moment, our amazing UM CS theory lab is generally eager to recruit postdocs. We formally advertise any opportunities on the CS theory jobs website. Please also feel free to contact me or any faculty member who is a good fit for your research plans.

Current students at the U of M: I'm always glad to meet with you and chat about anything, including but not limited to courses, research collaborations, general academic and professional advice, and concerns and misconduct. To reach out and schedule an appointment, simply send me an email and I'll get back to you as soon as I can. We can also have a virtual meeting if you prefer. I am an Individual with Reporting Obligations (IRO). This means that I am obligated to share with the Equity, Civil Rights & Title IX Office any information disclosed to me about sexual assault, sexual/gender based harassment, intimate partner violence, stalking, violation of protective measures.

Letters of recommendation for graduate school applications: Please read my policies here.

Selected Publications (Complete List of Publications):

Mahdi Cheraghchi. Capacity Upper Bounds for Deletion-Type Channels. Journal of the ACM (JACM), 66(2):9, 2019. Extended abstract in Proceedings of the 50th ACM Symposium on Theory of Computing (STOC), 2018. [Journal, Conference, Preprint]
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 in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. [Journal, Conference, Preprint]
Mahdi Cheraghchi, Venkatesan Guruswami. Capacity of Non-Malleable Codes. IEEE Transactions on Information Theory 62(3), pp. 1097–1118, 2016. Extended abstract in Proceedings of Innovations in Theoretical Computer Science (ITCS) , 2014. [Journal, Conference, Preprint]
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 in Proceedings of Theory of Cryptography Conference (TCC), 2014. [Journal, Conference, Preprint]
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 in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2013. [Journal, Conference, Preprint]

Current Funding: I'm grateful to the NSF for their generous support of my work (NSF CAREER award CCF-2236931, NSF CCF-2107345, NSF CCF-2006455).

Teaching:

I'm grateful to have received a Vulcans Education Excellence Award!
At the University of Michigan:

EECS 572/EECS 598: Randomness and Computation (Fall 2020, Fall 2022)

EECS 475: Introduction to Cryptography (Winter 2020, Winter 2021, Winter 2022, Winter 2023, Fall 2023, Winter 2025, Winter 2026)

CSE 574/EECS 574: Computational Complexity (Fall 2021, Fall 2023, Winter 2025, Winter 2026)

EECS 498/598: Coding Theory for Theoretical Computer Science (Fall 2019)

At Imperial College London:

CO-202: Algorithms II (Autumn 2018)

CO-349: Information and Coding Theory (Autumn 2018, Autumn 2017, Autumn 2016 and Autumn 2015)

CO-484: Quantum Computation (Autumn 2017, Autumn 2016)

CO-145: Mathematical Methods (Autumn 2017, Autumn 2016 and Autumn 2015)

At MIT:

6.006: Introduction to Algorithms (Fall 2014, MIT)

6.045: Automata, Computability, and Complexity (Spring 2014, MIT)

At CMU:

15-859: Information theory and its applications in theory of computation (Spring 2013, Carnegie Mellon University)

Current and Past Program Committee Memberships: ITC 2025, ISIT 2025, Asiacrypt 2024, ISIT 2024, RANDOM 2023, ITC (Information Theoretic Cryptography) 2023, ISIT 2023, ITW 2022, RANDOM 2021, ISIT 2021, IMA Cryptography and Coding 2021, ITW 2020, MFCS 2020, ITC (Information Theoretic Cryptography) 2020, ISIT 2020, ISIT 2019, ISIT 2018, RANDOM 2016.
Current editorial: IEEE BITS, IEEE Transactions on Communications.
Current Postdoc:

Harsha Srimath Tirumala

Current Ph.D. Students:

Alexandra Veliche

Past Ph.D. Students:

Dimitrios Myrisiotis (graduated in 2021)

Dissertation: The Complexity and Applications of Circuit Minimization.
Current position: Research Fellow at CNRS@CREATE LTD., Singapore.

João Ribeiro (graduated in 2021)

Dissertation: Coding Against Synchronisation and Related Errors.
Current position: Assistant Professor of CS at the University of Lisbon, Portugal.

I received my PhD in Computer Science from EPFL, Switzerland, where I worked as a research assistant in the Laboratory of Algorithms (ALGO) under supervision of Amin Shokrollahi.

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.

Some random links:

Official University of Michigan entry,
CSTheory.StackExchange: Q&A on Theoretical Computer Science research (my profile there),
Complexity Zoo: An encyclopedia of computational complexity classes,
Infinite Seinfeld,
Online Commodore 64,
Watch a movie in ASCII,
My public key (or search on a key server such as this or this; fingerprint: D56A 607C 6A70 E345 E02D 2A4B 6CAF DBB7 9F5B 0C54).
Send me anonymous feedback!

(Disclaimer: This is my personal website, and any opinions expressed in this website are solely my own.)

The local "date" in Iran is now ! (Thanks to my old friend Mahmood for the conversion script.)

Last Updated on February 2025