# 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).