Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
We study whether lower bounds against constant-depth algebraic circuits computing the Permanent over finite fields (Limaye-Srinivasan-Tavenas, J. ACM 2025; Forbes, CCC 2024) are ha…
cs.CC2025
Lower Bounds against the Ideal Proof System in Finite Fields
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu +1
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,…