|
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, who introduced me to research in TCS. My current research interests include computational complexity, query complexity, communication complexity, Boolean function analysis. I'm also broadly interested in algorithms, 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
67th IEEE Symposium on Foundations of Computer Science (FOCS) 2026, Best Paper Award.
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
Things I've been thinking about.
Mathematics
|
Programming
|
Teaching
- Teaching Assistant, COMS 4236: Introduction to Computational Complexity, Columbia University (Fall 2026)
- Teaching Assistant, CPSC 420: Advanced Algorithm Design and Analysis, UBC (2025W2)
- Teaching Assistant, CPSC 421: Introduction to the Theory of Computation, UBC (2025W1)
- Teaching Assistant, CPSC 320: Intermediate Algorithm Design and Analysis, UBC (2024W1, 2025S2)
Last updated:
