|
Rain Zimin Yang (杨子民)I am a first-year PhD student in the Theory of Computation group at Columbia University. 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, communication complexity, Boolean function analysis, and algorithms. I'm also broadly interested in automata theory, quantum computing and parallel algorithms. I competed in the ICPC World Finals in 2025, and will compete again in 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, CPSC 420: Advanced Algorithm Design and Analysis, University of British Columbia (2025W2)
- Teaching Assistant, CPSC 421: Introduction to the Theory of Computation, University of British Columbia (2025W1)
- Teaching Assistant, CPSC 320: Intermediate Algorithm Design and Analysis, University of British Columbia (2024W1, 2025S2)
Last updated: