Rain Zimin Yang (杨子民)

I am an incoming PhD student in Computer Science at Columbia University, beginning in Fall 2026. I completed a BSc in Computer Science and Mathematics at the University of British Columbia, where I worked with Professor Daochen Wang.
My research interests include computational complexity, query complexity, Boolean function complexity, and algorithms.

I also competed in the ICPC World Finals in 2025 and 2026.

CV · Linkedin

Research

Rational degree is polynomially related to degree
Robin Kothari, Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang
To appear in IEEE Symposium on Foundations of Computer Science (FOCS), 2026.

We prove that \(\deg(f) \leq \widetilde{O}(\operatorname{rdeg}(f)^3)\) for every Boolean function \(f\), resolving a 1994 open problem of Nisan and Szegedy attributed to Fortnow.

Blog

I'll mainly write about some papers I read, and talk about solutions to selected competitive programming problems I solved (listed in reverse chronological order).

Mathematics

(02/13/2026) Notes on Certificate Complexity, Quantum and Classical
(02/01/2026) Rational Rank Conjecture?
(01/19/2026) A Simple Proof of Hall's Theorem using Max-flow Min-cut
(12/12/2025) Non-deterministic Degree of Parity without Symmetrization
(05/01/2025) Sensitivity Theorem
(04/21/2025) A Lower Bound on the Non-deterministic Degree of Boolean Functions

Competitive Programming

(03/30/2026) Charles' Blog and Joel's Blog on NAC 2026
(12/18/2025) System of Difference Constraints Problem
(12/01/2025) Solution to Educational Codeforces Round 133 Problem E
(07/15/2025) Solution to Manthan, Codefest 19 Problem F
(05/29/2025) Solution to Codeforces Round 804 Problem D
(04/30/2025) Solution to Codeforces Round 682 Problem E
(04/23/2025) Solution to Educational Codeforces Round 137 Problem F
(04/11/2025) Solution to North American Invitational Programming Contest Problem A
(04/08/2025) Solution to Codeforces Round 1016 Problem G

Teaching

Teaching Assistant (UBC), CPSC 420: Advanced Algorithm Design and Analysis (2025W2)
Teaching Assistant (UBC), CPSC 421: Introduction to the Theory of Computation (2025W1)
Teaching Assistant (UBC), CPSC 320: Intermediate Algorithm Design and Analysis (2024W1, 2025S2)

Last updated: