Jiatu Li

According to our database, Jiatu Li authored at least 22 papers between 2020 and 2026.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2026

A Theory for Probabilistic Polynomial-Time Reasoning.

Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams

Electron. Colloquium Comput. Complex., 2026

Identity Testing for Circuits with Exponentiation Gates.

Jiatu Li, Mengdi Wu

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance.

Zhengyi Guo, Jiatu Li, Wenpin Tang, David D. Yao

CoRR, September, 2025

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$.

Lijie Chen, Jiatu Li, Igor C. Oliveira

Log. Methods Comput. Sci., 2025

On the Time Complexity of Feasible Proofs.

Jiatu Li

Electron. Colloquium Comput. Complex., 2025

An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists.

Jiatu Li

Electron. Colloquium Comput. Complex., 2025

The Structure of Catalytic Space: Capturing Randomness and Time via Compression.

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin.

Lijie Chen, Jiatu Li, Jingxun Liang

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S¹₂.

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography.

Yilei Chen, Jiatu Li

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness.

Jiatu Li, Edward Pyne, Roei Tell

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Reverse Mathematics of Complexity Lower Bounds.

Lijie Chen, Jiatu Li, Igor C. Oliveira

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms.

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

Electron. Colloquium Comput. Complex., 2023

Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.

Jiatu Li, Igor C. Oliveira

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.

Rahul Ilango, Jiatu Li, R. Ryan Williams

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms.

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

3.1<i>n</i> - <i>o</i>(<i>n</i>) circuit lower bounds for explicit functions.

Jiatu Li, Tianqi Yang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity.

Zhiyuan Fan, Jiatu Li, Tianqi Yang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.

Lijie Chen, Jiatu Li, Tianqi Yang

Proceedings of the 37th Computational Complexity Conference, 2022

2021

3.1n - o(n) Circuit Lower Bounds for Explicit Functions.

Jiatu Li, Tianqi Yang

Electron. Colloquium Comput. Complex., 2021

The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs.

Zhiyuan Fan, Jiatu Li, Tianqi Yang

Electron. Colloquium Comput. Complex., 2021

2020

Formalization of PAL·S5 in Proof Assistant.

Jiatu Li

CoRR, 2020