Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JIAQI LU:
All reports by Author Jiaqi Lu:

TR26-277 | 26th October 2026
Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

Meta-Mathematics of Algebraic Complexity

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while ... more >>>


TR25-134 | 19th September 2025
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

AC$^0$[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard

We study whether lower bounds against constant-depth algebraic circuits computing the Permanent over finite fields (Limaye–Srinivasan–Tavenas [J. ACM, 2025] and Forbes [CCC’24]) are hard to prove in certain proof systems. We focus on a DNF formula that expresses that such lower bounds are hard for constant-depth algebraic proofs. Using an ... more >>>


TR25-080 | 20th June 2025
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret

Lower Bounds against the Ideal Proof System in Finite Fields

Lower bounds against strong algebraic proof systems and specifically fragments of the Ideal Proof System (IPS), have been obtained in an ongoing line of work. All of these bounds, however, are proved only over large (or characteristic 0) fields,1 yet finite fields are the more natural setting for propositional proof ... more >>>




ISSN 1433-8092 | Imprint