All reports by Author Tuomas Hakoniemi:

__
TR22-055
| 23rd April 2022
__

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret#### 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, we show that the subset-sum variant $\sum_{i,j,k,l\in[n]} z_{ijkl}x_ix_jx_kx_l-\beta = 0$, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as ... more >>>