Published in ITCS, 2026
We introduce an identity testing problem inspired by machine learning compiler design and analyze a simple randomized algorithm. The algorithm is implemented in Mirage and works well in practice.
Recommended citation: Jiatu Li, Mengdi Wu. Identity Testing for Circuits with Exponentiation Gates. ITCS, 2026.
Download Paper
Published in STOC, 2025
We prove that Arthur-Merlin protocols with exponential time and a sub-exponential advice requires maximum circuit complexity. Previously, maximum lower bounds are known only for classes in the second level of the polynomial-time hierarchy.
Recommended citation: Lijie Chen, Jiatu Li, Jingxun Liang. Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin. STOC, 2025.
Download Paper | Download Slides | Download Bibtex
Published in STOC, 2025
We prove two unconditional structural results about catalytic computation: CL \(\cap\) P = CLP and CBPL = CL.
Recommended citation: James Cook, Jiatu Li, Ian Mertz, Edward Pyne. The Structure of Catalytic Space: Capturing Randomness and Time via Compression. STOC, 2025.
Download Paper | Download Bibtex
Published in FOCS, 2024
We show that with respect to the theory PV, certain lower bounds about communication complexity and Turing machines are equivalent to basic mathematical principles such as the Pigeonhole Principle.
Recommended citation: Lijie Chen, Jiatu Li, Igor C. Oliveira. Reverse Mathematics of Complexity Lower Bounds. FOCS, 2024.
Download Paper | Download Slides | Download Bibtex
Published in FOCS, 2024
This paper discusses connections between common concepts in the theory of pseudorandomness: distinguishers, predictors, and certification. Most interestingly, we obtain a new prBPP-complete problem related to derandomizing a lemma of Yao.
Recommended citation: Jiatu Li, Edward Pyne, Roei Tell. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. FOCS, 2024.
Download Paper | Download Slides | Download Bibtex
Published in STOC, 2024
This is a follow up work of the STOC 2023 paper with Rahul Ilango and Ryan Williams. We prove stronger hardness results by using more specific cryptographic assumptions.
Recommended citation: Yilei Chen, Jiatu Li. Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. STOC, 2024.
Download Paper | Download Slides | Download Bibtex
Published in STOC, 2023
Following a recent breakthrough of Pich and Santhanam (2021), we prove unprovability of strong complexity lower bounds in the the theory PV and even stronger theories.
Recommended citation: Jiatu Li, Igor C. Oliveira. Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic. STOC, 2023.
Download Paper | Download Slides | Download Bibtex
Published in STOC, 2023
We show that the range avoidance problem is hard for deterministic algorithms, assuming NP \(\ne\) coNP and the existence of indistinguishability obfuscation. With a similar approach, we also obtain unprovability results in bounded arithmetic.
Recommended citation: Rahul Ilango, Jiatu Li, Ryan Williams. Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. STOC, 2023.
Download Paper | Download Slides | Download Bibtex
Published in STOC, 2023
We provide unconditional NP-oracle algorithms for solving certain Range Avoidance Problem. This can be viewed as a generalization of ACC circuit lower bounds proved by Ryan Williams.
Recommended citation: Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren. Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms. STOC, 2023.
Download Paper | Download Slides | Download Bibtex
Published in CCC, 2022
A follow-up work on the STOC 2022 PRF paper, provide an even more efficient hash function construction and use it to show hardness magnification results.
Recommended citation: Lijie Chen, Jiatu Li, Tianqi Yang. Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. CCC, 2022.
Download Paper | Download Bibtex
Published in STOC, 2022
We obtained the exact circuit complexity of computing pseudorandom functions in various circuit models. We also use these construction to explain the difficulty of proving circuit lower bounds.
Recommended citation: Zhiyuan Fan, Jiatu Li, Tianqi Yang. The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity. STOC, 2022.
Download Paper | Download Bibtex
Published in STOC, 2022
We prove that an explicit function in P requires \(3.1n-o(n)\) size to compute by general circuits. This improves an earlier \((3+1/86)n-o(n)\) lower bound for the same function.
Recommended citation: Jiatu Li, Tianqi Yang. 3.1n-o(n) Circuit Lower Bounds for Explicit Functions. STOC, 2022.
Download Paper | Download Bibtex
Published in LMCS, 2025
We show unconditional unprovability of complexity upper and lower bounds in intuitionistic bounded arithmetic.
Recommended citation: Lijie Chen, Jiatu Li, Igor C. Oliveira. On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$. LMCS, 2025, Volume 21, Issue 3.
Download Paper | Download Bibtex