Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
We prove exponential lower bounds on the resolution proofs of some tautologies, based on rectangular grid graphs. More specifically, we show a 2/sup /spl Omega/(n)/ lower bound for any resolution proof of the mutilated chessboard problem on a 2n/spl times/2n chessboard as well as for the Tseitin tautology (G. Tseitin, 1968) based on the n/spl times/n rectangular grid graph. The former result answers a 35 year old conjecture by J. McCarthy (1964).
Dantchev, S., & Riis, S. (2001). Planar tautologies hard for resolution. In 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada ; proceedings (220-229). https://doi.org/10.1109/sfcs.2001.959896
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 42nd IEEE Symposium of Foundations of Computer Science |
Publication Date | 2001-10 |
Deposit Date | Feb 27, 2008 |
Publicly Available Date | Nov 1, 2010 |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 220-229 |
Book Title | 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada ; proceedings. |
DOI | https://doi.org/10.1109/sfcs.2001.959896 |
Public URL | https://durham-repository.worktribe.com/output/1698019 |
Published Conference Proceeding
(233 Kb)
PDF
Copyright Statement
© 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Sherali-Adams and the binary encoding of combinatorial principles
(2020)
Presentation / Conference Contribution
Resolution and the binary encoding of combinatorial principles
(2019)
Presentation / Conference Contribution
Simplicial Complex Entropy
(2017)
Presentation / Conference Contribution
Sublinear-Time Algorithms for Tournament Graphs
(2009)
Presentation / Conference Contribution
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
(2007)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search