Sitemap
A list of all the posts and pages found on the site. For you robots out there, there is an XML version available for digesting as well.
Pages
Posts
Future Blog Post
Published:
This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.
Blog Post number 4
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 3
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 2
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 1
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
publications
3.1n-o(n) Circuit Lower Bounds for Explicit Functions
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
The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity
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
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
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
Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms
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
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
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
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
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
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
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
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
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
Reverse Mathematics of Complexity Lower Bounds
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
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
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
Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin
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
On the Unprovability of Circuit Size Bounds in Intuitionistic \(S^1_2\)
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
Identity Testing for Circuits with Exponentiation Gates
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
teaching
Teaching experience 1
Undergraduate course, University 1, Department, 2014
This is a description of a teaching experience. You can use markdown like any other post.
Teaching experience 2
Workshop, University 1, Department, 2015
This is a description of a teaching experience. You can use markdown like any other post.