Posted on

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, fragments of Peano that captures 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.

Experience

  • Undergraduate Student: Tsinghua University (2019-)
  • Undergraduate Research Intern: University of Warwick (2022.3-2022.7), Advised by Dr. Igor Carboni Oliveira
  • Undergraduate Research Intern: Shanghai Qi Zhi Institute (2022.8-2022.9), Advised by Dr. Yilei Chen

How to contact me?

If you have any questions or comments about my papers, essays, and any other projects, please feel free to contact me. I will be more than happy to hear from anyone interested in my works.

My works

Research papers

In theoretical computer science, the authors are usually listed in alphabetical order.

  • Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.
    • A joint work with Lijie Chen and Tianqi Yang.
    • In Computational Complexity Conference (CCC 2022).
    • Full version: https://eccc.weizmann.ac.il/report/2022/086/
    • Summary. We construct an explicit, uniform, randomness efficient, and low-complexity hash function. It is used to prove the following hardness magnification result: if there is a sparse language in NP that is not computable by $2.01n$ size probabilistic circuits, then NP is not contained in SIZE$[n^k]$.
  • The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity.
    • A joint work with Zhiyuan Fan and Tianqi Yang.
    • In 54th ACM Symposium on Theory of Computing (STOC 2022).
    • Full version: https://eccc.weizmann.ac.il/report/2021/125/
    • Online talk by me: https://www.youtube.com/watch?v=QcBypyG6oMU&t=451s
    • Summary. We give tight bounds to compute PRFs in general $\mathsf{B}_2$ circuit (in size), $\mathsf{NC}_1$ circuits (in size and depth) and $\mathsf{TC}_0$ circuits (in wire). Inspired by the natural proof barrier and our results, we demonstrate a barrier for bootstrapping results (e.g. hardness magnification) in complexity theory.
  • $3.1n−o(n)$ Circuit Lower Bounds for Explicit Functions.

Other projects

  • Formalization of PAL·S5 in Proof Assistant.
  • Formalization of a theorem in a competitive programming problem.
  • Cutepiler: A Compiler for a C-like Language.
  • Hyper OS: An Operating System Simulator in C++.
    • Github: https://github.com/tqyaaaaang/Hyper-OS
    • A joint work with Tianqi Yang.
    • Summary. An operating system simulator for teaching and research use in C++. It contains basic virtual hardwares (such as CPU, APIC, MMU, etc) and a tiny kernel (including process scheduling and paging).

Notes, talks, and essays

  • A Quick Introduction to Mathematical Logic.
    • Note: https://ljt12138.github.io/2020/05/05/logic-note/
    • Summary. A note on classical results about propositional logic, first-order logic, proof system and (basic) model theory. It covers completeness theorem of first-order logic, compactness theorem and G¨odel’s incompleteness theorem.
  • The Application of Non-Programming Problems in Competitive Programming Training (in Chinese).

Interesting facts about me

  • My name, Li Jiatu, is the same as the Chinese translation of Ricardo. My parents choose the name when they are reading The Capital of Karl Marx, in which the name David Ricardo occurs constantly.