[Proof Complexity] New preprint

[Sam Buss]

Dear colleagues,

A preliminary version of a paper

"Short Refutations for the Equivalence-Chain Principle for Constant-Depth
Formulas"

by Ramyaa and myself is now available online at
http://www.math.ucsd.edu/~sbuss/ResearchWeb/AndOrTrees/. Comments are
appreciated.

  Best regards, Sam

----
Abstract: We consider tautologies expressing equivalence-chain
properties in the spirit of Thapen and Krajicek, which
are candidates for exponentially separating
depth $k$ and depth $k+1$ Frege proof systems.
We formulate a special case where the initial
member of the equivalence chain is fully specified
and the equivalence-chain implications
are actually equivalences.  This special case is
shown to lead to polynomial size resolution refutations.
Thus it cannot be used for separating depth $k$ and
depth $k+1$ propositional systems.
We state some Hastad switching lemma conditions
that restrict the possible propositional proofs
in more general situations.
----