I am Jiatu Li (李嘉图), a second-year graduate student at MIT theory group, advised by Ryan Williams. Before that, I was an undergraduate student at "Yao Class", Institute for Interdisciplinary Information Science (IIIS), Tsinghua University, during which I worked with Igor C. Oliveira at Warwick and Yilei Chen at Tsinghua University.

My research focuses on proving intrinsic hardness of computation (i.e. circuit complexity), proof systems (i.e. proof complexity), and understanding why this research direction is so hard (i.e. meta-complexity).

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

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 or Buss's theories for polynomial-time hierarchy? Can we separate Jerabek's theory for approximate counting and Cook's PV? Can we identify the relative strengths of combinatorial principles and theorems as a feasible analogy of the program of Reverse Mathematics? Partial results: APC vs PV, reverse mathematics, unprovability, unprovability'
• 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? Partial results: upper bound, lower bound 1, lower bound 2
• Proving unconditional complexity lower bounds (e.g. MW18, Chen23, CHR23, Li23) and derandomization results (e.g. CLORS23). Partial results: catalytic, general, PRFs

I am also interested in writing formal (i.e. computer verified) mathematical proofs in Coq and Lean (see logic). 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).

Selected Publication

• Reverse Mathematics of Complexity Lower Bounds. FOCS 2024 (to appear), invited to SICOMP special issue. Lijie Chen, Jiatu Li, Igor C. Oliveira.
• The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity. STOC 2022 (Best Student Paper). Zhiyuan Fan, Jiatu Li, Tianqi Yang.