6 papers
The Weak Rank Principle: Lower Bounds and Applications
Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren +1
Given two symbolic matrices and of dimensions and , the *weak rank principle* (WRank) states the equation is unsatisfiable when and ra…
Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments.…
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…
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,…
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi [GP18]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propos…
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
Albert Atserias, Iddo Tzameret
The Schwartz-Zippel Lemma states that if a low-degree multivariate polynomial with coefficients in a field is not zero everywhere in the field, then it has few roots on every finit…