Mark Chen

About Me

I received BS in CS (Theory+Systems) from Columbia Engineering in May 2026, with exposures to math and physics as well.

I'm broadly interested in anything theory-related. As of now, I'm actively thinking about:

Individualized differential privacy with data, query, and budget adaptivities.
Average-case complexity and smoothed analysis of total search problems.

Fundamentally, I'm driven by privacy — the pursuit of "the right to be let alone". My interests in cryptography, privacy, and the theoretical foundations of related fields are instantiations of this fundamental drive.

Contact

Email: mark.chen@columbia.edu
GitHub: mychern
Google Scholar: link

Research

* equal contribution (alphabetically listed).
† Non-PhD-students who had contributed considerably listed alphabetically (i.e. everyone listed passes a certain contribution threshold), as per the convention of Columbia's Applied DP Infrastructure Lab led by Prof. Roxana Geambasu. As such, it doesn't imply equal contribution.

Publications

Big Bird: Resilient Privacy Budgeting Across Untrusted Web Domains

With Pierre Tholoniat, Alison Caulfield†, Giorgio Cavicchioli†, Benjamin Case, Asaf Cidon, Roxana Geambasu, Mathias Lécuyer, and Martin Thomson

SOSP '26

Big Bird extends on-device privacy budgeting for private ad measurement so that its differential privacy guarantee holds even when untrusted web domains mount Sybil attacks to deplete users' privacy budgets.

I contributed to formulating and proving the theory for Big Bird's global privacy budget management, including the data modeling, the sensitivity bounds, and the resilience-to-DoS-depletion theorem against Sybil attacks. Building on this analysis, I formalized the per-user-action quota counts that separate benign behaviors from Sybil ones and incorporated them into Big Bird's privacy and graceful-degradation analyses.

On the systems side, I implemented a third of the general DP budget API in Rust, by the time of first public release, that several parallel projects such as CityOS build on. I was also one of the two main contributors evaluating learning with labeled proportions across DP architectures, which helped convince the W3C Private Advertising Technology Working Group (PATWG) of our design.
Fun Facts
- Accepted to SOSP'26 with unanimous accepts, bypassing the PC discussion.
- A follow-up to the SOSP '24 paper Cookie Monster, which won the Honorable Mention for Distinguished Artifact.
- At the CS3 NSF site visit day workshop, our work received unanimous top-band rating.
- PATWG preliminarily approved adopting this work to their standardization, considered by major browsers including Firefox and Chrome.

Boolean Function Monotonicity Testing Requires (Almost) $n^{1/2}$ Queries

With Xi Chen, Hao Cui, William Pires, and Jonah Stockwell

Best Paper Award at STOC '26

We prove a nearly tight $\Omega(n^{1/2-c})$ lower bound for adaptive monotonicity testing of Boolean functions, which moved the lower bound that's been stuck for 10 years, solving an open problem standing for 30 years. We did so based on successfully breaking the barrier of the last construction into a constant number of levels (previous attempts fail to change the lower bound due to trivial attacks).

I contributed by proving most of the intermediate claims in the good case, as well as the good-outcome induction that bounds layer-by-layer information leakage in the new construction. I also took the initiative to prove a first version of the adaptivity hierarchy lower bound, where the construction gives tight bounds for any constant round of adaptivity.

The same construction and similar proofs also settle, up to a sub-polynomial gap, the complexity of testing both monotonicity and unateness in the relative-error model.
Fun Facts
- Mentioned in Professor Oded Goldreich's selection of property testing papers.

Manuscripts

With Peihan Liu, Alison Caulfield†, Rachel Cummings, Roxana Geambasu, Mathias Lécuyer, and Pierre Tholoniat

In Submission — NeurIPS '26

CityOS: Privacy Architecture for Urban Sensing

With Giorgio Cavicchioli, Navid S. Pargoo†, Shuren Xia†, Xiaotian Zhou†, Roxana Geambasu, Jason Nieh, and Jorge Ortiz

In Submission — OSDI '27

Talks & Posters

[Boolean Function Monotonicity Testing] STOC '26 Virtual Session Poster Talk [Poster]
[Boolean Function Monotonicity Testing] Hour-Long Talk at the Cornell Theory Group (in Ithaca) [Slides]
[Big Bird] Evaluating Optimization Queries: Methodology and Preliminary Results [PATWG issue, slides]
[Ind. Sparse Vector via Target Charging] Adaptive Individual Accounting with Target Charging [poster]
[Big Bird & CityOS] Privacy-Preserving Architecture: From W3C Standards to Smart Cities [poster]
[Average-Case Hardness of TFNP in ROM] Proof of Sequential Work / Verifiable Delay Functions in ROM [typed, written]

Survey Papers & Class Projects

(Spring 2025) Proof Complexity. “Equivalences between TFNP^dt and Low-Level Proof Systems with an example in $\mathbb{F}_2$-Nullstellensatz” [pdf]
(Spring 2024) Unconditional Lower Bounds & Derandomization. “Fractional Pseudorandom Generators and Bounded Fourier Tails: A Literature Review” [pdf]
(Spring 2024) Unconditional Lower Bounds & Derandomization. “Bounding Threshold Formulas using Multiparty Communication Complexity Techniques” [pdf]
(Spring 2024) Advanced Cryptography. “Path to a New Secure Reinforcement Learning Model — Explicit Construction as an IP and Cryptographic Implications” [pdf]

Teaching

Teaching Assistant

Duties include weekly office hours, grading, and occasionally contributing homework or exam questions.

Spring 2026

Intro to Cryptography (COMS 3262)

Columbia University — final enrollment: 29 students

Spring 2026

Analysis of Algorithms (CSOR 4231)

Columbia University — final enrollment: 130+ students

Fall 2023

Introduction to Computational Complexity (COMS 4236)

Columbia University — final enrollment: 30+ students

Fall 2023

Analysis of Algorithms (CSOR 4231)

Columbia University — final enrollment: 110+ students

Seminars & Talks Given

(Fall 2025) A Tasting of Interactive Proof Systems — notes coming soon.
(Spring 2025) Property Testing — notes coming soon.
(Summer 2024) Differential Privacy — 6 talks based on Prof. Gautam Kamath's course.
(Spring 2024) Quantum Complexity Theory — talk 1 (definitions & overview), talk 6 on QMA and Local Hamiltonian Problems (with Andrew Yang). Co-organized semester-long seminar with the Columbia Undergraduate Learning Seminar in TCS.
(Spring 2024) Cryptography ∩ TFNP — “The Journey from NP to TFNP Hardness” (with Akshat Yaparla); “Cryptographic Hardness of Finding Nash Equilibrium” (with Yizhi Huang).
(Spring 2024) Quantum Information Theory — two-hour talk from interactive proof systems to quantum cryptography.

Typed Notes & Scribing

(Spring 2024) COMS 6998 Unconditional Lower Bounds and Derandomization — week 5 (Håstad's Switching Lemma & $\mathbb{F}_2$ Polynomials), week 8 (Fourier Analysis, Sandwiching Approximator & Viola's Theorem)
(Spring 2024) MATH 3952 Undergraduate Math Seminar (Quantum Information Theory) — full scribe notes
(Spring 2024) COMS 6261 Advanced Cryptography (TFNP) — presentation

Programs

CS3 Summer High School Program — Why and how Cookie Monster tackles the ads attribution problem?
Columbia Math Directed Reading Program

Industry

Google

4× SWE intern

Summer 2025 — Google Ads Privacy and Data Governance (APDG)

Built data and interactive feedback pipelines to automate privacy documentation writing and review processes using experimental fine-tuned Gemini APIs.

Summer 2024 — YouTube Nitrate Pay-Gated Content Recommendation

Data pipeline construction and fine-tuning ML models for content recommendations.

Summer 2023 — Over-the-Top (OTT) Platform Service

Wrote an end-to-end DVR testing system for streaming services, reducing bug detection time from days to hours.

Summer 2022 — YouTube Commerce Payments Backend

Wrote RPC server features for non-recurring plan listing and fulfillment.

Venture Capitals

2020–2021

Gap year working on tech-focused early-stage investments

At Nantucket (Summer 2021), ZhenFund (Spring 2021), K2VC (Fall 2020), and Ivy Capital (Summer 2020). Besides managerial and investment analytical experiences, I built a portfolio management visualization tool (JavaScript) and a market research scraper (Python).

Recognitions

PhD

STOC'26 Best Paper Award
IC3 Hackathon 2nd Place Winner (2026) Came with a 0.5 ETH prize, for the “Trustless Agent” project based on this paper on agent property auditing; also won 3rd place for “Funniest Presentation.” For more detail, see the official post under “Hackathon Winners.”
Stanford School of Engineering Fellowship (covering first-year PhD costs, such as rotations, by the school)
Cornell Fellowship (exempted from required TAships during PhD)
UW Allen School Computer Science & Engineering Research Fellowship (CSERF) (for top first-year PhD admits, +$3,000/year stipend)
Yale Sterling Prize Fellowship (for top 4 first-year PhD admits, +$3,000/year stipend)

College

Johns Hopkins Hodson Trust Scholar (for top 20 first-year undergrad admits) — $156,000 scholarship over four years
UPenn Ben Franklin Scholar (for top first-year undergrad admits)
Putnam Competition — Score of 21, ranked ~769 (2023)
Google MLthon (for interns) Finalist
Tau Beta Pi Inductee — Top 12.5% of the graduating engineering class at the end of the third year
Magna Cum Laude — Top 5-15% of the graduating engineering class at the time of graduation

High School

Regeneron Science Talent Search 2020 Scholar [arXiv]
Shing-Tung Yau High School Science Awards — North America Regional 1st Prize; Global Honorable Mention (Top 10) in CS, 2018 [arXiv]
Michigan SEFMD, 2019 — State Second Prize in Engineering; First in Engineering Mechanics Category [arXiv]
Michigan SEFMD, 2018 — Category Honorable Mention [JBiSE]
AIME Qualifier

Misc

My role model is Alex Honnold. My favorite moment of his — that is the sheer obsession I want to have.

I spent two summers in high school painting and drawing and still do casual sketches. I play basketball and tennis for fun, enjoy walking around, getting coffee and boba.

My great grandfather was a Chinese history scholar who survived the Laogai through decades of hiding. I always remember him as a knowledgeable, positive man surrounded by books from his scholarly days in the 1930s–40s. His memory lives on in my habit of reading Wikipedia pages about Chinese history and digital records of ancient texts (through this great effort!). For trivia, I can match most Gregorian years to their corresponding Chinese era names.

Originally from Ningbo, I've lived in Shanghai and Beijing (China), Manchester / Auburn NH, Bloomfield Hills MI, New York City, and the SF Bay Area. I also studied briefly in Auckland, New Zealand and Paris, France.

I'm fluent in English and Mandarin, took Latin to AP level, and am currently learning French and Russian.

Relevant Coursework

Undergrad

CS — Theory: Advanced Cryptography (intersecting TFNP), Intro to Cryptography, Unconditional Lower Bounds & Derandomization, Computational Complexity, Analysis of Algorithms, Quantum Computing.

CS — Systems: Distributed Systems, Computer Networks, Competitive Programming, Blockchain, Databases, Systems Programming, Data Structures.

Mathematics: Modern Analysis I&II, Modern Algebra I&II, Functions of Complex Variables, Topology.

Physics: Accelerated Intro to Physics I&II (Kleppner & Kolenkow for Mechanics; Purcell & Morin for E&M; quantum mechanics via A. P. French).