Basic information

I am Jiatu Li (李嘉图), a fourth-year undergraduate student in the Yao Class, Institute for Interdisciplinary Information Science (IIIS), Tsinghua University. My research interest is about circuit complexity, proof complexity, and cryptography. I am currently interested in the following problems:

The strength of Bounded Arithmetic, the fragments of Peano that capture the complexity of reasoning (see, e.g., Youtube Talk by Sam Buss). Can we prove strong lower bounds in Cook’s theory PV$_1$ or Buss’s theory $S^1_2$? Can we separate Jerabek’s theory APC$_1$ and Cook’s PV$_1$? Can we identify the relative strengths of combinatorial principles and theorems as a feasible analogy of the program of Reverse Mathematics?
The complexity of the Range Avoidance Problem (see Kor21, RSW22). What is the computational complexity of finding a non-output of an $n$-input $(n+1)$-output circuit? What if the circuit is a restricted one, say, an AC$_0$ circuit?

As complexity theorists, our mission is to liberate the warriors trying to solve inherently hard problems and use their stories to alleviate insomnia for cryptographers (see, e.g., Cryptographers Seldom Sleep Well).

I am also interested in writing formal (i.e. computer verified) mathematical proofs in Coq and Lean. Although it seems to be incredible nowadays, I believe that proof assistants will eventually be able to help mathematicians in their research (if mathematicians are not completely replaced by something like GPT-256, see, e.g., ChatGPT).

I am currently applying to Ph.D. programs in theoretical computer science (2023 Fall), see my CV.

I would also like to advertize my excellent friends and collaborators at Tsinghua University, from whom I learnt a lot on research and study. They are: Zihan Hu (theory), Yizhi Huang (theory), Tianqi Yang (theory), and Yaxin Tu (theory), in alphabetic order, as well as my girlfriend Mengdi Wu (system).