I am a fourth-year computer science PhD student at Columbia University, where I am a member of the Theory Group and the Crypto Lab. I am fortunate to be co-advised by Tal Malkin and Mihalis Yannakakis. I'm interested in practically motivated theoretical problems, especially in the areas of cryptography, privacy, and complexity. Topics I've worked on include watermarks for language models, cryptographic protocols for distributed settings (often blockchains), and differential privacy in the U.S. Census.
I earned an Sc.B. in Mathematics-Computer Science from Brown University, where I was very lucky to work with Megumi Ando and Eli Upfal.
Below, authors are listed in alphabetical order unless they clearly aren't, or unless it's otherwise noted.
You can also find my papers on my dblp and Google Scholar pages.
Pseudorandom Error-Correcting Codes. M. Christ, S. Gunn. 2024. [ePrint, arxiv]
Undetectable Watermarks for Language Models. M. Christ, S. Gunn, O. Zamir. 2023. [ePrint, arxiv, Slides] To appear at RWC 2024.
Cornucopia: Distributed Randomness Beacons at Scale. M. Christ, K. Choi, J. Bonneau. 2023. [ePrint]
Accountable Secret Leader Election. M. Christ, W. McKelvie, K. Choi, J. Bonneau, T. Malkin. 2023.
SoK: Zero-Knowledge Range Proofs. M. Christ, F. Baldimtsi, K. Chalkias, D. Maram, A. Roy, J. Wang. 2023. [ePrint]
Limits on Revocable Proof Systems, with Applications to Stateless Blockchains. M. Christ, J. Bonneau, Financial Cryptography 2023. [ePrint, a16z crypto talk, a16z crypto blog post]
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. M. Christ, M. Yannakakis, STOC 2023. [arxiv, STOC talk]
Differential Privacy and Swapping: Examining De-Identification's Impact on Minority Representation and Privacy Preservation in the U.S. Census. M. Christ*, S. Radway*, S.M. Bellovin, IEEE S&P 2022. [pdf, IEEE, Columbia Engineering article] (* denotes equal contribution)
Poly Onions: Achieving Anonymity in the Presence of Churn. M. Ando, M. Christ, A. Lysyanskaya, T. Malkin, TCC 2022. [ePrint, TCC talk]
The Impact of De-Identification on Single-Year-of-Age Counts in the U.S. Census. S. Radway, M. Christ, TPDP 2023.
Differential Privacy and Swapping: Examining De-Identification's Impact on Minority Representation and Privacy Preservation in the U.S. Census. M. Christ*, S. Radway*, S.M. Bellovin, TPDP 2022. (* denotes equal contribution)
Counting Kindergarteners: De-identification's Impact on Student Representation. M. Christ, S. Radway, 2020 Census Data Products: Workshop on the Demographic and Housing Characteristics Files 2022 (hosted by the National Academies and Committee on National Statistics).
On the impossibility of stateless blockchains. M. Christ, J. Bonneau. a16z crypto blog 2023.
Zero-Knowledge Range Proofs: Proving Where Your Secret Lies. M. Christ, F. Baldimtsi, K. Chalkias, D. Maram, A. Roy, J. Wang. Mysten Labs blog 2023.
Leader Election from Randomness Beacons and Other Strategies. M. Christ, V. Nikolaenko, J. Bonneau. a16z crypto blog 2022.
Theory of Cryptography Conference '22: Field Notes. M. Christ. a16z crypto blog 2022.
Google: Student Researcher. Spring 2024.
Mysten Labs: Intern, cryptography group. Summer 2023.
Simons Institute, Meta-Complexity Program: Visiting Student. Spring 2023.
a16z crypto research: Intern. Summer and Fall 2022.
Email: mchrist at cs dot columbia dot edu