Yichuan Wang 王一川

Photo by Lijie Chen.

I am Yichuan Wang, a 1st-year PhD student in the Theory Group of the Department of Electrical Engineering and Computer Sciences at UC Berkeley, where I am advised by Lijie Chen and Avishay Tal. My research interest lies broadly in Theoretical Computer Science (TCS)When I talk about TCS, I usually refer to Computational Complexity Theory..

I completed my undergraduate degree at Institute for Interdisciplinary Information Sciences, Tsinghua University, where I was fortunate to be working with Yilei Chen and Kuan Cheng. In Spring 2024, I visited UC Berkeley and worked with my current PhD advisors.

I studied Mathematical Olympiad during high school and won the gold medal with the unique perfect score in the 62nd International Mathematical Olympiad (2021).

In Theoretical Computer Science (TCS), people study the powers and limits of theoretical computation models. Our ultimate goal is to understand the essence of computation, especially the essence of computational intractability, where our understanding remains limited. I am looking forward to seeing that after 50 (or 100) years, humans will have proved \(\mathsf{P}\neq\mathsf{PSPACE}\) (or even the existence of OWF) and also developed a good intuition on where the computational intractability comes from, which may reshape human's understanding of our universe.

I appreciate the works in the last century that formalized concepts like "computation" and "algorithm". I am also impressed by the recent paradigm of studying the connections between the power of a computational model and the hardness of its meta-computational problems, as exemplified by works such as [Wil10] and [CIKK16].

I have previously published works on space-bounded derandomization and streaming lower bounds.

• Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits;
  Lijie Chen, Avishay Tal, Yichuan Wang;
  In STOC 2026.
• Separating RAM and Multitape Turing Machines with Short Random Oracles;
  Lijie Chen, Yichuan Wang.
• Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits;
  Hanlin Ren, Yichuan Wang, Yan Zhong;
  In ITCS 2026, Best Student Paper Award. [Hanlin's slides]
• Tight Streaming Lower Bounds for Deterministic Approximate Counting;
  Yichuan Wang;
  In SODA 2025, Best Student Paper Award. [slides]
• A Study of Error Reduction Polynomials;
  Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz.
• \(\textsf{BPL}\subseteq\textsf{L-AC}^1\);
  Kuan Cheng, Yichuan Wang;
  In CCC 2024. [slides]