TY - GEN

T1 - Graph expansion, tseitin formulas and resolution proofs for CSP

AU - Itsykson, Dmitry

AU - Oparin, Vsevolod

PY - 2013/11/29

Y1 - 2013/11/29

N2 - We study the resolution complexity of Tseitin formulas over arbitrary rings in terms of combinatorial properties of graphs. We give some evidence that an expansion of a graph is a good characterization of the resolution complexity of Tseitin formulas. We extend the method of Ben-Sasson and Wigderson of proving lower bounds for the size of resolution proofs to constraint satisfaction problems under an arbitrary finite alphabet. For Tseitin formulas under the alphabet of cardinality d we provide a lower bound d e(G)-k for tree-like resolution complexity that is stronger than the one that can be obtained by the Ben-Sasson and Wigderson method. Here k is an upper bound on the degree of the graph and e(G) is the graph expansion that is equal to the minimal cut such that none of its parts is more than twice bigger than the other. We give a formal argument why a large graph expansion is necessary for lower bounds. Let G = âŒ

AB - We study the resolution complexity of Tseitin formulas over arbitrary rings in terms of combinatorial properties of graphs. We give some evidence that an expansion of a graph is a good characterization of the resolution complexity of Tseitin formulas. We extend the method of Ben-Sasson and Wigderson of proving lower bounds for the size of resolution proofs to constraint satisfaction problems under an arbitrary finite alphabet. For Tseitin formulas under the alphabet of cardinality d we provide a lower bound d e(G)-k for tree-like resolution complexity that is stronger than the one that can be obtained by the Ben-Sasson and Wigderson method. Here k is an upper bound on the degree of the graph and e(G) is the graph expansion that is equal to the minimal cut such that none of its parts is more than twice bigger than the other. We give a formal argument why a large graph expansion is necessary for lower bounds. Let G = âŒ

UR - http://www.scopus.com/inward/record.url?scp=84888223953&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38536-0-14

DO - 10.1007/978-3-642-38536-0-14

M3 - Conference contribution

AN - SCOPUS:84888223953

SN - 9783642385353

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 162

EP - 173

BT - Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013

T2 - 8th International Computer Science Symposium in Russia, CSR 2013

Y2 - 25 June 2013 through 29 June 2013

ER -