Standard
Simplified and Improved Separations Between Regular and General Resolution by Lifting. / Vinyals, Marc; Elffers, Jan; Johannsen, Jan; Nordström, Jakob.
Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings. ed. / Luca Pulina; Martina Seidl. Springer, 2020. p. 182-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12178 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Vinyals, M, Elffers, J, Johannsen, J
& Nordström, J 2020,
Simplified and Improved Separations Between Regular and General Resolution by Lifting. in L Pulina & M Seidl (eds),
Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12178 LNCS, pp. 182-200, 23rd International Conference on Theory and Applications of Satisfiability Testing, SAT 2020, Virtual, Online,
03/07/2020.
https://doi.org/10.1007/978-3-030-51825-7_14APA
Vinyals, M., Elffers, J., Johannsen, J.
, & Nordström, J. (2020).
Simplified and Improved Separations Between Regular and General Resolution by Lifting. In L. Pulina, & M. Seidl (Eds.),
Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings (pp. 182-200). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 12178 LNCS
https://doi.org/10.1007/978-3-030-51825-7_14Vancouver
Vinyals M, Elffers J, Johannsen J
, Nordström J.
Simplified and Improved Separations Between Regular and General Resolution by Lifting. In Pulina L, Seidl M, editors, Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings. Springer. 2020. p. 182-200. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12178 LNCS).
https://doi.org/10.1007/978-3-030-51825-7_14Author
Vinyals, Marc ; Elffers, Jan ; Johannsen, Jan ; Nordström, Jakob. / Simplified and Improved Separations Between Regular and General Resolution by Lifting. Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings. editor / Luca Pulina ; Martina Seidl. Springer, 2020. pp. 182-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12178 LNCS).
Bibtex
@inproceedings{e90fac72f1f1481e9e1b31f86e92d7b7,
title = "Simplified and Improved Separations Between Regular and General Resolution by Lifting",
abstract = "We give a significantly simplified proof of the exponential separation between regular and general resolution of Alekhnovich et al. (2007) as a consequence of a general theorem lifting proof depth to regular proof length in resolution. This simpler proof then allows us to strengthen the separation further, and to construct families of theoretically very easy benchmarks that are surprisingly hard for SAT solvers in practice.",
author = "Marc Vinyals and Jan Elffers and Jan Johannsen and Jakob Nordstr{\"o}m",
year = "2020",
doi = "10.1007/978-3-030-51825-7_14",
language = "English",
isbn = "9783030518240",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "182--200",
editor = "Luca Pulina and Martina Seidl",
booktitle = "Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings",
address = "Switzerland",
note = "23rd International Conference on Theory and Applications of Satisfiability Testing, SAT 2020 ; Conference date: 03-07-2020 Through 10-07-2020",
}
RIS
TY - GEN
T1 - Simplified and Improved Separations Between Regular and General Resolution by Lifting
AU - Vinyals, Marc
AU - Elffers, Jan
AU - Johannsen, Jan
AU - Nordström, Jakob
PY - 2020
Y1 - 2020
N2 - We give a significantly simplified proof of the exponential separation between regular and general resolution of Alekhnovich et al. (2007) as a consequence of a general theorem lifting proof depth to regular proof length in resolution. This simpler proof then allows us to strengthen the separation further, and to construct families of theoretically very easy benchmarks that are surprisingly hard for SAT solvers in practice.
AB - We give a significantly simplified proof of the exponential separation between regular and general resolution of Alekhnovich et al. (2007) as a consequence of a general theorem lifting proof depth to regular proof length in resolution. This simpler proof then allows us to strengthen the separation further, and to construct families of theoretically very easy benchmarks that are surprisingly hard for SAT solvers in practice.
UR - http://www.scopus.com/inward/record.url?scp=85088278995&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-51825-7_14
DO - 10.1007/978-3-030-51825-7_14
M3 - Article in proceedings
AN - SCOPUS:85088278995
SN - 9783030518240
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 182
EP - 200
BT - Theory and Applications of Satisfiability Testing – SAT 2020 - 23rd International Conference, Proceedings
A2 - Pulina, Luca
A2 - Seidl, Martina
PB - Springer
T2 - 23rd International Conference on Theory and Applications of Satisfiability Testing, SAT 2020
Y2 - 3 July 2020 through 10 July 2020
ER -
