Hi! I am Heda Chen. I study complexity theory.
- My research interests spread out around structures, i.e., capturing the structural properties hidden in various objects (e.g., graphs, Boolean functions, polynomial-time computable functions, etc.) and exploiting them.
- (When we say the "structure" of a problem, we mean the "shape" formed by YES instances inside the space of all instances. e.g., the shape of \(\{x \in \{0, 1\}^n: f(x) = 1\}\) inside \(\{0, 1\}^n\).)
- Meta-Complexity. Meta-complexity problems are those themselves asking complexities (of concrete problems), e.g., MCSP (Minimum Circuit Size Problem), MKtP (Minimum time-bounded Kolmogorov Complexity Problem). In this field, we study and characterize complexity classes using the complexity of meta-complexity problems.
- Pseudorandomness and Derandomization. If a problem can be solved by an algorithm with randomness, it means "the structure of this problem could be approximately characterized and captured, if additional dimensions are attached to the input space". Derandomization is to precisely capture the structure of the problem itself (and thus remove these additional dimensions, aka randomness); and pseudorandomness is to reduce the amount of extra dimensions needed. These topics are indeed not that relevant to the exact concept of randomness, but to reduce the uncertainty (or "approximation") by studying the inherent structure of the problem.
- A board interest grown from this includes Structural Complexity Theory, Combinatorics and even Type Theory.
- Currently a senior undergraduate@SJTU, ACM Honor Class 2020; will join UofT CS Theory Group in 2024 fall.
- I'm available at hedachen03@gmail.com. Please feel free to drop me a line.
Outside Research
- I enjoy playing badminton🏸, billiards🎱, riding🚴 and walking🚶.
- Thinking problems while riding/walking makes me more focused and creative🤔.
- Seeking for a mountain bike🚲 in Toronto.
- I love listening to various kind of music🎵. Symphony is the best.
- I like reading📖, particularly those around social science topics (e.g. psychology, behavioral science, sociology).
- My currently favorite book: The Image: A Guide to Pseudo-Events in America (by Daniel J. Boorstin).
- Writing✏️ my thoughts down is a skill I have long been desiring and am now keeping improving.
- Including random thoughts which brust anywhere at anytime, as well as expositions for academic research results.
- The Sense of Style (by Steven Pinker) is a great book that had helped me a lot.
- Talking💬 with someone resonating with me is joyful, so if you are interested by my text and wanna share your thoughts, please feel free to drop me a line.