Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On small-depth Frege proofs for Tseitin for grids
KTH, Superseded Departments (pre-2005), Mathematics. KTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2017 (English)In: 2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), IEEE, 2017, 97-108 p.Conference paper, Published paper (Refereed)
Abstract [en]

We prove a lower bound on the size of a small depth Frege refutation of the Tseitin contradiction on the grid. We conclude that polynomial size such refutations must use formulas of almost logarithmic depth.

Place, publisher, year, edition, pages
IEEE, 2017. 97-108 p.
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-220658DOI: 10.1109/FOCS.2017.18ISI: 000417425300009ISBN: 978-1-5386-3464-6 OAI: oai:DiVA.org:kth-220658DiVA: diva2:1172107
Conference
58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA
Note

QC 20180109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
MathematicsNumerical Analysis and Computer Science, NADA
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf