Standard

Graph expansion, tseitin formulas and resolution proofs for CSP. / Itsykson, Dmitry; Oparin, Vsevolod.

Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. 2013. p. 162-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7913 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Itsykson, D & Oparin, V 2013, Graph expansion, tseitin formulas and resolution proofs for CSP. in Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7913 LNCS, pp. 162-173, 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russian Federation, 25/06/13. https://doi.org/10.1007/978-3-642-38536-0-14

APA

Itsykson, D., & Oparin, V. (2013). Graph expansion, tseitin formulas and resolution proofs for CSP. In Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013 (pp. 162-173). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7913 LNCS). https://doi.org/10.1007/978-3-642-38536-0-14

Vancouver

Itsykson D, Oparin V. Graph expansion, tseitin formulas and resolution proofs for CSP. In Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. 2013. p. 162-173. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-38536-0-14

Author

Itsykson, Dmitry ; Oparin, Vsevolod. / Graph expansion, tseitin formulas and resolution proofs for CSP. Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. 2013. pp. 162-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e7c194bb976e4e90b6f8e4badae9919f,
title = "Graph expansion, tseitin formulas and resolution proofs for CSP",
abstract = "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 = {\^a}{\OE}",
author = "Dmitry Itsykson and Vsevolod Oparin",
year = "2013",
month = nov,
day = "29",
doi = "10.1007/978-3-642-38536-0-14",
language = "English",
isbn = "9783642385353",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "162--173",
booktitle = "Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013",
note = "8th International Computer Science Symposium in Russia, CSR 2013 ; Conference date: 25-06-2013 Through 29-06-2013",

}

RIS

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 -

ID: 49786016