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