Showing cs.CCShow all
2 papers · 1 filter
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,…
cs.CC2022
Simple Hard Instances for Low-Depth Algebraic Proofs
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically,…