Basic information

I am Jiatu Li (李嘉图), a first-year graduate student at MIT theory group. I obtained my Bachelor degree from ``Yao Class”, Institute for Interdisciplinary Information Science (IIIS), Tsinghua University.

My research interest is about circuit complexity, proof complexity, and cryptography. Recently, I am interested in the following concrete directions:

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