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:

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