Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGEBRAIC PROOFS:
Reports tagged with algebraic proofs:
TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

#### The Strength of Multilinear Proofs

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

TR10-097 | 16th June 2010
Iddo Tzameret

#### Algebraic Proofs over Noncommutative Formulas

Revisions: 1

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>

TR18-184 | 5th November 2018
Iddo Tzameret, Stephen Cook

#### Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

TR22-055 | 23rd April 2022
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

#### Simple Hard Instances for Low-Depth Algebraic Proofs

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 >>>

ISSN 1433-8092 | Imprint