Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGEBRAIC PROOF SYSTEMS:
Reports tagged with algebraic proof systems:
TR97-048 | 13th October 1997
Soren Riis, Meera Sitharam

#### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

The semantics of decision problems are always essentially independent of the
underlying representation. Thus the space of input data (under appropriate
indexing) is closed
under action of the symmetrical group $S_n$ (for a specific data-size)
and the input-output relation is closed under the action of $S_n$.
more >>>

TR07-078 | 11th August 2007
Ran Raz, Iddo Tzameret

#### Resolution over Linear Equations and Multilinear Proofs

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>

TR19-142 | 23rd October 2019
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

#### Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

We introduce the `binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>

ISSN 1433-8092 | Imprint