Soren Riis, Meera Sitharam

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

Ran Raz, Iddo Tzameret

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

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

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