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
Monotone Circuit Lower Bounds from Resolution
Microsoft Res, Redmond, WA 98052 USA..
Harvard Univ, Cambridge, MA 02138 USA..
MIT, Cambridge, MA 02139 USA..
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
2018 (English)In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 902-911Conference paper, Published paper (Refereed)
Abstract [en]

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols-or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY , 2018. p. 902-911
Keywords [en]
Circuit complexity, proof complexity
National Category
Embedded Systems
Identifiers
URN: urn:nbn:se:kth:diva-244571DOI: 10.1145/3188745.3188838ISI: 000458175600077Scopus ID: 2-s2.0-85049886695OAI: oai:DiVA.org:kth-244571DiVA, id: diva2:1294868
Conference
50th Annual ACM Symposium on Theory of Computing, STOC 2018; Los Angeles; United States; 25 June 2018 through 29 June 2018
Note

QC 20190308

Available from: 2019-03-08 Created: 2019-03-08 Last updated: 2019-03-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Sokolov, Dmitry

Search in DiVA

By author/editor
Sokolov, Dmitry
By organisation
Theoretical Computer Science, TCS
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 76 hits
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