About me
I am Jiatu Li (李嘉图), a fourth-year graduate student at the fantastic MIT theory group, where I’m fortunate to be advised by Prof. Ryan Williams.
I obtained my Bachelor’s degree from the “Yao Class”, Institute for Interdisciplinary Information Science (IIIS), Tsinghua University.
Research Interests
My research is in circuit complexity, meta-complexity, and proof complexity. A few concrete directions I’m currently excited about:
The strength of bounded arithmetic
The fragments of Peano arithmetic that capture the complexity of reasoning (see, e.g., the 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 Jeřábek’s theory APC\(_1\) from Cook’s PV\(_1\)? Can we rank combinatorial principles by the strength needed to prove them, as a feasible analogue of Reverse Mathematics?
Our resultsthe APX₁ theoryAPC vs PVreverse mathematicsunprovabilityunprovability'
The complexity of range avoidance
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? And what changes when the circuit is restricted — say, to AC\(_0\)?
Our resultsupper boundlower bound 1lower bound 2
Sleep aid for cryptographers
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). For interested cryptographers, see our recently discovered sleep aid medication at SNARGs for NP from unprovability of mathematical theorems.
Selected Publications1
Reverse Mathematics of Complexity Lower Bounds
Lijie Chen, Jiatu Li, Igor C. Oliveira
FOCS 2024 · invited to the SICOMP special issue · featured in Quanta Magazine
Zhiyuan Fan, Jiatu Li, Tianqi Yang
STOC 2022 · Danny Lewin Best Student Paper (co-winner)
News
Interesting facts about me
- My name, Li Jiatu, is the same as the Chinese translation of Ricardo. My parents chose the name when they were reading The Capital of Karl Marx, in which the name David Ricardo occurs constantly.
- I learned Go (the chess game, not the programming language) when I was a kid and achieved amateur four-dan. Recently, I’m interested in playing go again. My ID on Fox Weiqi is jiatu1li (6d). I am a member of the MIT Go Club and you could probably catch me in the meetings (check https://www.meetup.com/massgo/ for the schedule).
Other papers are also good. I love all of them equally! ↩