vente ... |

Jump to content
Endre søk PrimeFaces.cw("InputText","widget_formSmash_searchField",{id:"formSmash:searchField",widgetVar:"widget_formSmash_searchField"}); Søk $(function(){PrimeFaces.cw("DefaultCommand","widget_formSmash_j_idt123",{id:"formSmash:j_idt123",widgetVar:"widget_formSmash_j_idt123",target:"formSmash:searchButton",scope:"formSmash:simpleSearch"});}); Søk PrimeFaces.cw("CommandButton","widget_formSmash_searchButton",{id:"formSmash:searchButton",widgetVar:"widget_formSmash_searchButton"});
Kun dokumenter med fulltekst i DiVA
PrimeFaces.cw("Fieldset","widget_formSmash_search",{id:"formSmash:search",widgetVar:"widget_formSmash_search",toggleable:true,collapsed:true,toggleSpeed:500,behaviors:{toggle:function(ext) {PrimeFaces.ab({s:"formSmash:search",e:"toggle",f:"formSmash",p:"formSmash:search"},ext);}}});
PrimeFaces.cw("InputText","widget_formSmash_upper_j_idt526",{id:"formSmash:upper:j_idt526",widgetVar:"widget_formSmash_upper_j_idt526"}); Fler formatPrimeFaces.cw("InputText","widget_formSmash_upper_j_idt536",{id:"formSmash:upper:j_idt536",widgetVar:"widget_formSmash_upper_j_idt536"}); Fler språkSkapa PrimeFaces.cw("CommandButton","widget_formSmash_upper_j_idt545",{id:"formSmash:upper:j_idt545",widgetVar:"widget_formSmash_upper_j_idt545"}); Stäng PrimeFaces.cw("CommandButton","widget_formSmash_upper_j_idt546",{id:"formSmash:upper:j_idt546",widgetVar:"widget_formSmash_upper_j_idt546"});
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:upper:j_idt515",widgetVar:"citationDialog",width:"800",height:"600"});});
5 10 20 50 100 250 $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt558",{id:"formSmash:j_idt558",widgetVar:"widget_formSmash_j_idt558",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt558",e:"change",f:"formSmash",p:"formSmash:j_idt558"},ext);}}});});
Standard (Relevans) Forfatter A-Ø Forfatter Ø-A Tittel A-Ø Tittel Ø-A Type publikasjon A-Ø Type publikasjon Ø-A Eldste først Nyeste først Skapad (Eldste først) Skapad (Nyeste først) Senast uppdaterad (Eldste først) Senast uppdaterad (Nyeste først) Disputationsdatum (tidligste først) Disputationsdatum (siste først) $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt568",{id:"formSmash:j_idt568",widgetVar:"widget_formSmash_j_idt568",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt568",e:"change",f:"formSmash",p:"formSmash:j_idt568"},ext);}}});});
Standard (Relevans) Forfatter A-Ø Forfatter Ø-A Tittel A-Ø Tittel Ø-A Type publikasjon A-Ø Type publikasjon Ø-A Eldste først Nyeste først Skapad (Eldste først) Skapad (Nyeste først) Senast uppdaterad (Eldste først) Senast uppdaterad (Nyeste først) Disputationsdatum (tidligste først) Disputationsdatum (siste først) $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt571",{id:"formSmash:j_idt571",widgetVar:"widget_formSmash_j_idt571",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt571",e:"change",f:"formSmash",p:"formSmash:j_idt571"},ext);}}});});
alle i siden PrimeFaces.cw("CommandButton","widget_formSmash_j_idt579",{id:"formSmash:j_idt579",widgetVar:"widget_formSmash_j_idt579"}); 250 framåt PrimeFaces.cw("CommandButton","widget_formSmash_j_idt580",{id:"formSmash:j_idt580",widgetVar:"widget_formSmash_j_idt580"});
Rydd valg PrimeFaces.cw("CommandButton","widget_formSmash_j_idt582",{id:"formSmash:j_idt582",widgetVar:"widget_formSmash_j_idt582"});
$(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_j_idt585",{id:"formSmash:j_idt585",widgetVar:"widget_formSmash_j_idt585",target:"formSmash:selectHelpLink",showEffect:"blind",hideEffect:"fade",showCloseIcon:true});});
$(function(){PrimeFaces.cw("DataList","widget_formSmash_items_resultList",{id:"formSmash:items:resultList",widgetVar:"widget_formSmash_items_resultList"});});
PrimeFaces.cw("InputText","widget_formSmash_lower_j_idt949",{id:"formSmash:lower:j_idt949",widgetVar:"widget_formSmash_lower_j_idt949"}); Fler formatPrimeFaces.cw("InputText","widget_formSmash_lower_j_idt959",{id:"formSmash:lower:j_idt959",widgetVar:"widget_formSmash_lower_j_idt959"}); Fler språkSkapa PrimeFaces.cw("CommandButton","widget_formSmash_lower_j_idt968",{id:"formSmash:lower:j_idt968",widgetVar:"widget_formSmash_lower_j_idt968"}); Stäng PrimeFaces.cw("CommandButton","widget_formSmash_lower_j_idt969",{id:"formSmash:lower:j_idt969",widgetVar:"widget_formSmash_lower_j_idt969"});
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:lower:j_idt938",widgetVar:"citationDialog",width:"800",height:"600"});});

Begrens søket

RefereraExporteraLink til resultatlisten
http://kth.diva-portal.org/smash/resultList.jsf?query=&language=no&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A31369+OR+0000-0002-2700-4285%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt503_recordPermLink",{id:"formSmash:upper:j_idt503:recordPermLink",widgetVar:"widget_formSmash_upper_j_idt503_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt503_j_idt505",{id:"formSmash:upper:j_idt503:j_idt505",widgetVar:"widget_formSmash_upper_j_idt503_j_idt505",target:"formSmash:upper:j_idt503:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Referera

Referensformatapa ieee modern-language-association-8th-edition vancouver Annet format $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt521",{id:"formSmash:upper:j_idt521",widgetVar:"widget_formSmash_upper_j_idt521",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt521",e:"change",f:"formSmash",p:"formSmash:upper:j_idt521",u:"formSmash:upper:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association-8th-edition
- vancouver
- Annet format

Språkde-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Annet språk $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt532",{id:"formSmash:upper:j_idt532",widgetVar:"widget_formSmash_upper_j_idt532",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt532",e:"change",f:"formSmash",p:"formSmash:upper:j_idt532",u:"formSmash:upper:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Annet språk

Utmatningsformathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt542",{id:"formSmash:upper:j_idt542",widgetVar:"widget_formSmash_upper_j_idt542"});});

- html
- text
- asciidoc
- rtf

Treff pr side

- 5
- 10
- 20
- 50
- 100
- 250

Sortering

- Standard (Relevans)
- Forfatter A-Ø
- Forfatter Ø-A
- Tittel A-Ø
- Tittel Ø-A
- Type publikasjon A-Ø
- Type publikasjon Ø-A
- Eldste først
- Nyeste først
- Skapad (Eldste først)
- Skapad (Nyeste først)
- Senast uppdaterad (Eldste først)
- Senast uppdaterad (Nyeste først)
- Disputationsdatum (tidligste først)
- Disputationsdatum (siste først)

- Standard (Relevans)
- Forfatter A-Ø
- Forfatter Ø-A
- Tittel A-Ø
- Tittel Ø-A
- Type publikasjon A-Ø
- Type publikasjon Ø-A
- Eldste først
- Nyeste først
- Skapad (Eldste først)
- Skapad (Nyeste først)
- Senast uppdaterad (Eldste først)
- Senast uppdaterad (Nyeste først)
- Disputationsdatum (tidligste først)
- Disputationsdatum (siste først)

Merk

Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.

1. Cumulative Space in Black-White Pebbling and Resolution Alwen, Joëlet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt609",{id:"formSmash:items:resultList:0:j_idt609",widgetVar:"widget_formSmash_items_resultList_0_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); de Rezende, Susanna F.KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Cumulative Space in Black-White Pebbling and Resolution2017Inngår i: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:0:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_0_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:0:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 2. Narrow proofs may be maximally long Atserias, A.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt609",{id:"formSmash:items:resultList:1:j_idt609",widgetVar:"widget_formSmash_items_resultList_1_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Narrow proofs may be maximally long2014Inngår i: Proceedings of the Annual IEEE Conference on Computational Complexity, 2014, s. 286-297Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:1:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_1_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size nω(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size nO(ω) is essentially tight. Moreover, our lower bounds can be generalized to polynomial calculus resolution (PCR) and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. Our results do not extend all the way to Lasserre, however-the formulas we study have Lasserre proofs of constant rank and size polynomial in both n and w.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:1:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 3. Clique Is Hard on Average for Regular Resolution Atserias, Albert PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt606",{id:"formSmash:items:resultList:2:j_idt606",widgetVar:"widget_formSmash_items_resultList_2_j_idt606",onLabel:"Atserias, Albert ",offLabel:"Atserias, Albert ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt609",{id:"formSmash:items:resultList:2:j_idt609",widgetVar:"widget_formSmash_items_resultList_2_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Bonacina, IlarioUniv Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..de Rezende, Susanna F.KTH, Skolan för elektroteknik och datavetenskap (EECS).Lauria, MassimoSapienza Univ Roma, Dept Stat Sci, Rome, Italy..Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS).Razborov, AlexanderUniv Chicago, Chicago, IL 60637 USA.;Steklov Math Inst, Moscow, Russia..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Clique Is Hard on Average for Regular Resolution2018Inngår i: 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, s. 866-877Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:2:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_2_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that for k << (4)root n regular resolution requires length n(Omega(k)) to establish that an Erdos Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n(Omega(k)) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:2:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 4. Narrow Proofs May Be Maximally Long Atserias, Albertet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt609",{id:"formSmash:items:resultList:3:j_idt609",widgetVar:"widget_formSmash_items_resultList_3_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoNordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Narrow Proofs May Be Maximally Long2016Inngår i: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 17, nr 3, artikkel-id 19Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:3:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_3_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n(Omega(w)). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n(O(w)) is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:3:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 5. Some trade-off results for polynomial calculus Beck, C.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt609",{id:"formSmash:items:resultList:4:j_idt609",widgetVar:"widget_formSmash_items_resultList_4_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Tang, B.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Some trade-off results for polynomial calculus2013Inngår i: STOC '13 Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, Association for Computing Machinery (ACM), 2013, s. 813-822Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:4:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_4_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We present size-space trade-offs for the polynomial calculus (PC) and polynomial calculus resolution (PCR) proof systems. These are the first true size-space trade-offs in any algebraic proof system, showing that size and space cannot be simultaneously optimized in these models. We achieve this by extending essentially all known size-space trade-offs for resolution to PC and PCR. As such, our results cover space complexity from constant all the way up to exponential and yield mostly superpolynomial or even exponential size blow-ups. Since the upper bounds in our trade-offs hold for resolution, our work shows that there are formulas for which adding algebraic reasoning on top of resolution does not improve the trade-off properties in any significant way. As byproducts of our analysis, we also obtain trade-offs between space and degree in PC and PCR exactly matching analogous results for space versus width in resolution, and strengthen the resolution trade-offs in [Beame, Beck, and Impagliazzo '12] to apply also to k-CNF formulas.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:4:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 6. A Space Hierarchy for k-DNF Resolution Ben-Sasson, Eliet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt609",{id:"formSmash:items:resultList:5:j_idt609",widgetVar:"widget_formSmash_items_resultList_5_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A Space Hierarchy for k-DNF Resolution2009Inngår i: Electronic Colloquium on Computational Complexity, ISSN 1433-8092, Vol. 16Artikkel i tidsskrift (Fagfellevurdert)7. Short proofs may be spacious Ben-Sasson, Eliet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt609",{id:"formSmash:items:resultList:6:j_idt609",widgetVar:"widget_formSmash_items_resultList_6_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Short proofs may be spacious: An optimal separation of space and length in resolution2008Inngår i: Proc. Annu. IEEE Symp. Found. Comput. Sci. FOCS, 2008, s. 709-718Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:6:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_6_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space. In this paper we resolve the question by answering it negatively in the strongest possible way. We show that there are families of 6-CNF formulas of size n, for arbitrarily large n, that have resolution proofs of length O(n) but for which any proof requires space Ω(n/log n). This is the strongest asymptotic separation possible since any proof of length O(n) can always be transformed into a proof in space O(n/log n). Our result follows by reducing the space complexity of so called pebbling formulas over a directed acyclic graph to the black-white pebbling price of the graph. The proof is somewhat simpler than previous results (in particular, those reported in [Nordström 2006, Nordström and Håstad 2008]) as it uses a slightly different flavor of pebbling formulas which allows for a rather straightforward reduction of proof space to standard black-white pebbling price.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:6:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 8. Understanding Space in Resolution Ben-Sasson, Eliet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt609",{id:"formSmash:items:resultList:7:j_idt609",widgetVar:"widget_formSmash_items_resultList_7_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs2009Inngår i: Electronic Colloquium on Computational Complexity, ISSN 1433-8092, Vol. 16Artikkel i tidsskrift (Fagfellevurdert)9. Supercritical space-width trade-offs for resolution Berkholz, C.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt609",{id:"formSmash:items:resultList:8:j_idt609",widgetVar:"widget_formSmash_items_resultList_8_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Supercritical space-width trade-offs for resolution2016Inngår i: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:8:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_8_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width resolution proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben- Sasson 2009], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov 2016]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordström 2008].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:8:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 10. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps Berkholz, Christophet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt609",{id:"formSmash:items:resultList:9:j_idt609",widgetVar:"widget_formSmash_items_resultList_9_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps2016Inngår i: PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), Institute of Electrical and Electronics Engineers (IEEE), 2016, s. 267-276Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:9:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_9_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n(Omega(k/logk)). Our trade-offs also apply to first-order counting logic, and by the known connection to the k-dimensional Weisfeiler-Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov ' 16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the quantifier depth required to distinguish them.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:9:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 11. Supercritical space-width trade-offs for resolution Berkholz, Christophet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt609",{id:"formSmash:items:resultList:10:j_idt609",widgetVar:"widget_formSmash_items_resultList_10_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Supercritical space-width trade-offs for resolution2020Inngår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 49, nr 1, s. 98-118Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:10:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_10_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [E. Ben-Sasson, SIAM J. Comput., 38 (2009), pp. 2511-2525], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [A.A. Razborov, J. ACM, 63 (2016), 16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [E. Ben-Sasson and J. Nordström, Short proofs may be spacious: An optimal separation of space and length in resolution, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 2008, pp. 709-718].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:10:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 12. On the Semantics of Local Characterizations for Linear-Invariant Properties Bhatttacharyya, Arnabet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt609",{id:"formSmash:items:resultList:11:j_idt609",widgetVar:"widget_formSmash_items_resultList_11_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Grigorescu, ElenaNordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Semantics of Local Characterizations for Linear-Invariant Properties2011Artikkel i tidsskrift (Annet vitenskapelig)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:11:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_11_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A property of functions on a vector space is said to be linear-invariant if it is closed under linear transformations of the domain. Linear-invariant properties are some of the most well-studied properties in the field of property testing. Testable linear-invariant properties can always be characterized by socalled local constraints, and of late there has been a rapidly developing body of research investigating the testability of linear-invariant properties in terms of their descriptions using such local constraints. One problematic aspect that has been largely ignored in this line of research, however, is that syntactically distinct local characterizations need not at all correspond to semantically distinct properties. In fact, there are known fairly dramatic examples where seemingly infinite families of properties collapse into a small finite set that was already well-understood. In this work, we therefore initiate a systematic study of the semantics of local characterizations of linear-invariant properties. For such properties the local characterizations have an especially nice structure in terms of forbidden patterns on linearly dependent sets of vectors, which can be encoded formally as matroid constraints. We develop techniques for determining, given two such matroid constraints, whether these constraints encode identical or distinct properties, and show for a fairly broad class of properties that these techniques provide necessary and sufficient conditions for deciding between the two cases. We use these tools to show that recent (syntactic) testability results indeed provide an infiniti number of infinity strict hierarchies of (semantically) distinct testable locally characterized linear-invariant properties.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:11:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 13. On the Semantics of Local Characterizations for Linear-Invariant Properties Bhatttacharyya, Arnabet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_12_j_idt609",{id:"formSmash:items:resultList:12:j_idt609",widgetVar:"widget_formSmash_items_resultList_12_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Grigorescu, ElenaNordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Xie, NingPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Semantics of Local Characterizations for Linear-Invariant Properties2011Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_12_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:12:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_12_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A property of functions on a vector space is said to be linear-invariant if it is closed under linear transformations of the domain. Linear-invariant properties are some of the most well-studied properties in the field of property testing. Testable linear-invariant properties can always be characterized by socalled local constraints, and of late there has been a rapidly developing body of research investigating the testability of linear-invariant properties in terms of their descriptions using such local constraints. One problematic aspect that has been largely ignored in this line of research, however, is that syntactically distinct local characterizations need not at all correspond to semantically distinct properties. In fact, there are known fairly dramatic examples where seemingly infinite families of properties collapse into a small finite set that was already well-understood. In this work, we therefore initiate a systematic study of the semantics of local characterizations of linear-invariant properties. For such properties the local characterizations have an especially nice structure in terms of forbidden patterns on linearly dependent sets of vectors, which can be encoded formally as matroid constraints. We develop techniques for determining, given two such matroid constraints, whether these constraints encode identical or distinct properties, and show for a fairly broad class of properties that these techniques provide necessary and sufficient conditions for deciding between the two cases. We use these tools to show that recent (syntactic) testability results indeed provide an infinite number of infinite strict hierarchies of (semantically) distinct testable locally characterized linear-invariant properties

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:12:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 14. Hardness of Approximation in PSPACE and Separation Results for Pebble Games Chan, S. M.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt609",{id:"formSmash:items:resultList:13:j_idt609",widgetVar:"widget_formSmash_items_resultList_13_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordstrom, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Hardness of Approximation in PSPACE and Separation Results for Pebble Games2015Inngår i: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Institute of Electrical and Electronics Engineers (IEEE), 2015, s. 466-485Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:13:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_13_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond - Tompa and Raz - McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:13:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 15. Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity de Rezende, Susanna F. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt606",{id:"formSmash:items:resultList:14:j_idt606",widgetVar:"widget_formSmash_items_resultList_14_j_idt606",onLabel:"de Rezende, Susanna F. ",offLabel:"de Rezende, Susanna F. ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt609",{id:"formSmash:items:resultList:14:j_idt609",widgetVar:"widget_formSmash_items_resultList_14_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Meir, OrNordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Toniann, PitassiRobere, RobertVinyals, MarcPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lifting with Simple Gadgets and Applications to Circuit and Proof ComplexityManuskript (preprint) (Annet vitenskapelig)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:14:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_14_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems:

- We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomialline space if coefficients are restricted to be of polynomial magnitude.

- We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known.

An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:14:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 16. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling de Rezende, Susanna F. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt606",{id:"formSmash:items:resultList:15:j_idt606",widgetVar:"widget_formSmash_items_resultList_15_j_idt606",onLabel:"de Rezende, Susanna F. ",offLabel:"de Rezende, Susanna F. ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt609",{id:"formSmash:items:resultList:15:j_idt609",widgetVar:"widget_formSmash_items_resultList_15_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS. Univ Copenhagen, Copenhagen, Denmark.Meir, OrUniv Haifa, Haifa, Israel.Robere, RobertDIMACS, New Brunswick, NJ USA.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling2019Inngår i: Proceedings of the 34th Annual Computational Complexity Conference (CCC ’19), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2019, Vol. 137, s. 18:1-18:16Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:15:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_15_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if an only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:15:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 17. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs de Rezende, Susanna F. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt606",{id:"formSmash:items:resultList:16:j_idt606",widgetVar:"widget_formSmash_items_resultList_16_j_idt606",onLabel:"de Rezende, Susanna F. ",offLabel:"de Rezende, Susanna F. ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt609",{id:"formSmash:items:resultList:16:j_idt609",widgetVar:"widget_formSmash_items_resultList_16_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Risse, KilianKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Sokolov, DmitryPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs2020Inngår i: 35th Computational Complexity Conference (CCC 2020), Schloss Dagstuhl–Leibniz-Zentrum für Informatik , 2020, Vol. 169, s. 28-1Konferansepaper (Fagfellevurdert)18. How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity) de Rezende, Susanna F. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt606",{id:"formSmash:items:resultList:17:j_idt606",widgetVar:"widget_formSmash_items_resultList_17_j_idt606",onLabel:"de Rezende, Susanna F. ",offLabel:"de Rezende, Susanna F. ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt609",{id:"formSmash:items:resultList:17:j_idt609",widgetVar:"widget_formSmash_items_resultList_17_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)2016Inngår i: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2016, Vol. 2016, s. 295-304Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:17:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_17_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers. We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajicek ' 98], drawing on and extending techniques in [Raz and McKenzie ' 99] and [Goos et al. '15]. The communication lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic graphs. As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain an exponential separation between monotone-AC(i-1) and monotone-AC(i), improving exponentially over the superpolynomial separation in [Raz and McKenzie ' 99]. That is, we give an explicit Boolean function that can be computed by monotone Boolean circuits of depth log(i) n and polynomial size, but for which circuits of depth O (log(i-1) n) require exponential size.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:17:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 19. A cardinal improvement to pseudo-boolean solving Elffers, J.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt609",{id:"formSmash:items:resultList:18:j_idt609",widgetVar:"widget_formSmash_items_resultList_18_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A cardinal improvement to pseudo-boolean solving2020Inngår i: AAAI 2020 - 34th AAAI Conference on Artificial Intelligence, AAAI press , 2020, s. 1495-1503Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:18:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_18_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Pseudo-Boolean solvers hold out the theoretical potential of exponential improvements over conflict-driven clause learning (CDCL) SAT solvers, but in practice perform very poorly if the input is given in the standard conjunctive normal form (CNF) format. We present a technique to remedy this problem by recovering cardinality constraints from CNF on the fly during search. This is done by collecting potential building blocks of cardinality constraints during propagation and combining these blocks during conflict analysis. Our implementation has a non-negligible but manageable overhead when detection is not successful, and yields significant gains for some SAT competition and crafted benchmarks for which pseudo-Boolean reasoning is stronger than CDCL. It also boosts performance for some native pseudo-Boolean formulas where this approach helps to improve learned constraints. Copyright

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:18:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 20. Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers Elffers, Jan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt606",{id:"formSmash:items:resultList:19:j_idt606",widgetVar:"widget_formSmash_items_resultList_19_j_idt606",onLabel:"Elffers, Jan ",offLabel:"Elffers, Jan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt609",{id:"formSmash:items:resultList:19:j_idt609",widgetVar:"widget_formSmash_items_resultList_19_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Giráldez-Cru, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Vinyals, MarcTata Institute of Fundamental Research, Mumbai, India.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers2018Inngår i: Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018, Springer, 2018, Vol. 10929, s. 75-93Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:19:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_19_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study cdcl-cuttingplanes, Open-WBO, and Sat4j, three successful solvers from the Pseudo-Boolean Competition 2016, and evaluate them by performing experiments on crafted benchmarks designed to be trivial for the cutting planes (CP) proof system underlying pseudo-Boolean (PB) proof search but yet potentially tricky for PB solvers. Our experiments demonstrate severe shortcomings in state-of-the-art PB solving techniques. Although our benchmarks have linear-size tree-like CP proofs, and are thus extremely easy in theory, the solvers often perform quite badly even for very small instances. We believe this shows that solvers need to employ stronger rules of cutting planes reasoning. Even some instances that lack not only Boolean but also real-valued solutions are very hard in practice, which indicates that PB solvers need to get better not only at Boolean reasoning but also at linear programming. Taken together, our results point to several crucial challenges to be overcome in the quest for more efficient pseudo-Boolean solvers, and we expect that a further study of our benchmarks could shed more light on the potential and limitations of current state-of-the-art PB solving.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:19:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 21. Seeking practical CDCL insights from theoretical SAT benchmarks Elffers, Jan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt606",{id:"formSmash:items:resultList:20:j_idt606",widgetVar:"widget_formSmash_items_resultList_20_j_idt606",onLabel:"Elffers, Jan ",offLabel:"Elffers, Jan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt609",{id:"formSmash:items:resultList:20:j_idt609",widgetVar:"widget_formSmash_items_resultList_20_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Giráldez-Crú, JesúsKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Gocht, StephanKTH, Skolan för elektroteknik och datavetenskap (EECS).Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Simon, L.Université de Bordeaux, France.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Seeking practical CDCL insights from theoretical SAT benchmarks2018Inngår i: IJCAI International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2018, s. 1300-1308Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:20:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_20_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Over the last decades Boolean satisfiability (SAT) solvers based on conflict-driven clause learning (CDCL) have developed to the point where they can handle formulas with millions of variables. Yet a deeper understanding of how these solvers can be so successful has remained elusive. In this work we shed light on CDCL performance by using theoretical benchmarks, which have the attractive features of being a) scalable, b) extremal with respect to different proof search parameters, and c) theoretically easy in the sense of having short proofs in the resolution proof system underlying CDCL. This allows for a systematic study of solver heuristics and how efficiently they search for proofs. We report results from extensive experiments on a wide range of benchmarks. Our findings include several examples where theory predicts and explains CDCL behaviour, but also raise a number of intriguing questions for further study.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:20:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 22. Justifying All Differences Using Pseudo-Boolean Reasoning Elffers, Jan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt606",{id:"formSmash:items:resultList:21:j_idt606",widgetVar:"widget_formSmash_items_resultList_21_j_idt606",onLabel:"Elffers, Jan ",offLabel:"Elffers, Jan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt609",{id:"formSmash:items:resultList:21:j_idt609",widgetVar:"widget_formSmash_items_resultList_21_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Lund Univ, Lund, Sweden.;Univ Copenhagen, Copenhagen, Denmark..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Gocht, StephanLund Univ, Lund, Sweden.;Univ Copenhagen, Copenhagen, Denmark..McCreesh, CiaranUniv Glasgow, Glasgow, Lanark, Scotland..Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS. Univ Copenhagen, Copenhagen, Denmark.;KTH Royal Inst Technol, Stockholm, Sweden..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Justifying All Differences Using Pseudo-Boolean Reasoning2020Inngår i: Thirty-Fourth Aaai Conference On Artificial Intelligence, The Thirty-Second Innovative Applications Of Artificial Intelligence Conference And The Tenth Aaai Symposium On Educational Advances In Artificial Intelligence, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE , 2020, s. 1486-1494Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:21:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_21_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Constraint programming solvers support rich global constraints and propagators, which make them both powerful and hard to debug. In the Boolean satisfiability community, proof-logging is the standard solution for generating trustworthy outputs, and this has become key to the social acceptability of computer-generated proofs. However, reusing this technology for constraint programming requires either much weaker propagation, or an impractical blowup in proof length. This paper demonstrates that simple, clean, and efficient proof logging is still possible for the all-different constraint, through pseudo-Boolean reasoning. We explain how such proofs can be expressed and verified mechanistically, describe an implementation, and discuss the broader implications for proof logging in constraint programming.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:21:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 23. Trade-offs between time and memory in a tighter model of CDCL SAT solvers Elffers, Jan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt606",{id:"formSmash:items:resultList:22:j_idt606",widgetVar:"widget_formSmash_items_resultList_22_j_idt606",onLabel:"Elffers, Jan ",offLabel:"Elffers, Jan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt609",{id:"formSmash:items:resultList:22:j_idt609",widgetVar:"widget_formSmash_items_resultList_22_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Johannsen, J.Lauria, M.Magnard, T.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Trade-offs between time and memory in a tighter model of CDCL SAT solvers2016Inngår i: 19th International Conference on Theory and Applications of Satisfiability Testing, SAT 2016, Springer, 2016, s. 160-176Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:22:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_22_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A long line of research has studied the power of conflict- driven clause learning (CDCL) and how it compares to the resolution proof system in which it searches for proofs. It has been shown that CDCL can polynomially simulate resolution even with an adversarially chosen learning scheme as long as it is asserting. However, the simulation only works under the assumption that no learned clauses are ever forgot- ten, and the polynomial blow-up is significant. Moreover, the simulation requires very frequent restarts, whereas the power of CDCL with less frequent or entirely without restarts remains poorly understood. With a view towards obtaining results with tighter relations between CDCL and resolution, we introduce a more fine-grained model of CDCL that cap- tures not only time but also memory usage and number of restarts. We show how previously established strong size-space trade-offs for resolution can be transformed into equally strong trade-offs between time and memory usage for CDCL, where the upper bounds hold for CDCL with- out any restarts using the standard 1UIP clause learning scheme, and the (in some cases tightly matching) lower bounds hold for arbitrarily frequent restarts and arbitrary clause learning schemes.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:22:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 24. Divide and conquer Elffers, Jan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt606",{id:"formSmash:items:resultList:23:j_idt606",widgetVar:"widget_formSmash_items_resultList_23_j_idt606",onLabel:"Elffers, Jan ",offLabel:"Elffers, Jan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt609",{id:"formSmash:items:resultList:23:j_idt609",widgetVar:"widget_formSmash_items_resultList_23_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Divide and conquer: Towards faster pseudo-boolean solving2018Inngår i: IJCAI'18: Proceedings of the 27th International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2018, s. 1291-1299Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:23:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_23_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The last 20 years have seen dramatic improvements in the performance of algorithms for Boolean satisfiability-so-called SAT solvers-and today conflict-driven clause learning (CDCL) solvers are routinely used in a wide range of application areas. One serious short-coming of CDCL, however, is that the underlying method of reasoning is quite weak. A tantalizing solution is to instead use stronger pseudo-Boolean (PB) reasoning, but so far the promise of exponential gains in performance has failed to materialize-the increased theoretical strength seems hard to harness algorithmically, and in many applications CDCL-based methods are still superior. We propose a modified approach to pseudo-Boolean solving based on division instead of the saturation rule used in [Chai and Kuehlmann'05] and other PB solvers. In addition to resulting in a stronger conflict analysis, this also improves performance by keeping integer coefficient sizes down, and yields a very competitive solver as shown by the results in the Pseudo-Boolean Competitions 2015 and 2016.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:23:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 25. Space complexity in polynomial calculus Filmus, Y.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt609",{id:"formSmash:items:resultList:24:j_idt609",widgetVar:"widget_formSmash_items_resultList_24_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, M.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Thapen, N.Ron-Zewi, N.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Space complexity in polynomial calculus2012Inngår i: Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, IEEE , 2012, s. 334-344Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:24:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_24_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich et. al.'02], where the lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could refute any k-CNF formula in constant space. We prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied in [Alekhnovich et.al.~'02]. - For PCR, we prove an Omega(n) space lower bound for a bit wise encoding of the functional pigeonhole principle with m pigeons and n holes. These formulas have width O(log(n)), and hence this is an exponential improvement over [Alekhnovich et.al.~'02] measured in the width of the formulas. - We then present another encoding of the pigeonhole principle that has constant width, and prove an Omega(n) space lower bound in PCR for these formulas as well. - We prove an Omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHP(m, n) with m pigeons and n holes, and show that this is tight. - We prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not known to be the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:24:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 26. From small space to small width in resolution Filmus, Y.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt609",{id:"formSmash:items:resultList:25:j_idt609",widgetVar:"widget_formSmash_items_resultList_25_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Mikša, MladenKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, M.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); From small space to small width in resolution2015Inngår i: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 16, nr 4, artikkel-id 28Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:25:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_25_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of a Conjunctive Normal Form (CNF) formula is always an upper bound on the width needed to refute the formula. Their proof is beautiful but uses a nonconstructive argument based on Ehrenfeucht-Fraïssé games. We give an alternative, more explicit, proof that works by simple syntactic manipulations of resolution refutations. As a by-product, we develop a "black-box" technique for proving space lower bounds via a "static" complexitymeasure that works against any resolution refutation-previous techniques have been inherently adaptive. We conclude by showing that the related question for polynomial calculus (i.e., whether space is an upper bound on degree) seems unlikely to be resolvable by similarmethods.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:25:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 27. From small space to small width in resolution Filmus, Y.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_26_j_idt609",{id:"formSmash:items:resultList:26:j_idt609",widgetVar:"widget_formSmash_items_resultList_26_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Mikša, MladenKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); From small space to small width in resolution2014Inngår i: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2014, Vol. 25, s. 300-311Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_26_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:26:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_26_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools from finite model theory. We give an alternative, completely elementary, proof that works by simple syntactic manipulations of resolution refutations. As a by-product, we develop a "black-box" technique for proving space lower bounds via a "static" complexity measure that works against any resolution refutation-previous techniques have been inherently adaptive. We conclude by showing that the related question for polynomial calculus (i.e., whether space is an upper bound on degree) seems unlikely to be resolvable by similar methods.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:26:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 28. Towards an understanding of polynomial calculus Filmus, Yuvalet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt609",{id:"formSmash:items:resultList:27:j_idt609",widgetVar:"widget_formSmash_items_resultList_27_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Mikša, MladenKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Towards an understanding of polynomial calculus: New separations and lower bounds (extended abstract)2013Inngår i: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, nr PART 1, s. 437-448Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:27:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_27_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); During the last decade, an active line of research in proof complexity has been into the space complexity of proofs and how space is related to other measures. By now these aspects of resolution are fairly well understood, but many open problems remain for the related but stronger polynomial calculus (PC/PCR) proof system. For instance, the space complexity of many standard "benchmark formulas" is still open, as well as the relation of space to size and degree in PC/PCR. We prove that if a formula requires large resolution width, then making XOR substitution yields a formula requiring large PCR space, providing some circumstantial evidence that degree might be a lower bound for space. More importantly, this immediately yields formulas that are very hard for space but very easy for size, exhibiting a size-space separation similar to what is known for resolution. Using related ideas, we show that if a graph has good expansion and in addition its edge set can be partitioned into short cycles, then the Tseitin formula over this graph requires large PCR space. In particular, Tseitin formulas over random 4-regular graphs almost surely require space at least Ω(√n). Our proofs use techniques recently introduced in [Bonacina-Galesi '13]. Our final contribution, however, is to show that these techniques provably cannot yield non-constant space lower bounds for the functional pigeonhole principle, delineating the limitations of this framework and suggesting that we are still far from characterizing PC/PCR space.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:27:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 29. Space complexity in polynomial calculus Filmus, Yuvalet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt609",{id:"formSmash:items:resultList:28:j_idt609",widgetVar:"widget_formSmash_items_resultList_28_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordstrom, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Ron-Zewi, NogaThapen, NeilPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Space complexity in polynomial calculus2015Inngår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, nr 4, s. 1119-1153Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:28:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_28_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); During the last 10 to 15 years, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important concern in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers. There has been a relatively long sequence of papers on space in resolution, which is now reasonably well-understood from this point of view. For other proof systems of interest, however, such as polynomial calculus or cutting planes, progress has been more limited. Essentially nothing has been known about space complexity in cutting planes, and for polynomial calculus the only lower bound has been for conjunctive normal form (CNF) formulas of unbounded width in [Alekhnovich et al., SIAM J. Comput., 31 (2002), pp. 1184-1211], where the space lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could be able to refute any k-CNF formula in constant space. In this paper, we prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied by Alekhnovich et al.: (1) We prove an omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHPmn with m pigeons and n holes, and show that this is tight. (2) For PCR, we prove an omega(n) space lower bound for a bitwise encoding of the functional pigeonhole principle. These formulas have width O(log n), and hence this is an exponential improvement over Alekhnovich et al. measured in the width of the formulas. (3) We then present another encoding of the pigeonhole principle that has constant width, and prove an omega(n) space lower bound in PCR for these formulas as well. (4) Finally, we prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not obviously the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way, something that we believe can be useful when proving PCR space lower bounds for other well-studied formula families in proof complexity.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:28:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 30. Space Complexity in Polynomial Calculus Filmus, Yuvalet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt609",{id:"formSmash:items:resultList:29:j_idt609",widgetVar:"widget_formSmash_items_resultList_29_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Lauria, MassimoKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Ron-Zewi, NogaThapen, NeilPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Space Complexity in Polynomial Calculus2012Inngår i: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092, nr 132Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:29:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_29_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers.

There has been a relatively long sequence of papers on space in resolution, which is now reasonably well understood from this point of view. For other natural candidates to study, however, such as polynomial calculus or cutting planes, very little has been known. We are not aware of any nontrivial space lower bounds for cutting planes, and for polynomial calculus the only lower bound has been for CNF formulas of unbounded width in [Alekhnovich et al. '02], where the space lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could be able to refute any k-CNF formula in constant space.

In this paper, we prove several new results on space in polynomial calculus (PC), and in the extended proof system polynomial calculus resolution (PCR) studied in [Alekhnovich et al. '02]:

(1) We prove an Omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHP^m_n with m pigeons and n holes, and show that this is tight.

(2) For PCR, we prove an Omega(n) space lower bound for a bitwise encoding of the functional pigeonhole principle. These formulas have width O(log n), and hence this is an exponential improvement over [Alekhnovich et al. '02] measured in the width of the formulas.

(3) We then present another encoding of the pigeonhole principle that has constant width, and prove an Omega(n) space lower bound in PCR for these formulas as well.

(4) Finally, we prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not obviously the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way, something that we believe can be useful when proving PCR space lower bounds for other well-studied formula families in proof complexity.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:29:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 31. On division versus saturation in pseudo-boolean solving Gocht, Stephan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt606",{id:"formSmash:items:resultList:30:j_idt606",widgetVar:"widget_formSmash_items_resultList_30_j_idt606",onLabel:"Gocht, Stephan ",offLabel:"Gocht, Stephan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt609",{id:"formSmash:items:resultList:30:j_idt609",widgetVar:"widget_formSmash_items_resultList_30_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS. University of Copenhagen, Denmark.Yehudayoff, AmirTechnion - Israel Institute of Technology, Israel.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On division versus saturation in pseudo-boolean solving2019Inngår i: IJCAI International Joint Conference on Artificial Intelligence: Volume 2019-August, 2019, 2019, s. 1711-1718Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:30:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_30_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The conflict-driven clause learning (CDCL) paradigm has revolutionized SAT solving over the last two decades. Extending this approach to pseudo-Boolean (PB) solvers doing 0-1 linear programming holds the promise of further exponential improvements in theory, but intriguingly such gains have not materialized in practice. Also intriguingly, most PB extensions of CDCL use not the division rule in cutting planes as defined in [Cook et al.,'87] but instead the so-called saturation rule. To the best of our knowledge, there has been no study comparing the strengths of division and saturation in the context of conflict-driven PB learning, when all linear combinations of inequalities are required to cancel variables. We show that PB solvers with division instead of saturation can be exponentially stronger. In the other direction, we prove that simulating a single saturation step can require an exponential number of divisions. We also perform some experiments to see whether these phenomena can be observed in actual solvers. Our conclusion is that a careful combination of division and saturation seems to be crucial to harness more of the power of cutting planes

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:30:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 32. On the virtue of succinct proofs Huynh, Trinhet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt609",{id:"formSmash:items:resultList:31:j_idt609",widgetVar:"widget_formSmash_items_resultList_31_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity2012Inngår i: Proceedings of the Annual ACM Symposium on Theory of Computing, 2012, s. 233-247Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:31:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_31_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); An active line of research in proof complexity over the last decade has been the study of proof space and trade-offs between size and space. Such questions were originally motivated by practical SAT solving, but have also led to the development of new theoretical concepts in proof complexity of intrinsic interest and to results establishing nontrivial relations between space and other proof complexity measures. By now, the resolution proof system is fairly well understood in this regard, as witnessed by a sequence of papers leading up to [Ben-Sasson and Nordstrom 2008, 2011] and [Beame, Beck, and Impagliazzo 2012]. However, for other relevant proof systems in the context of SAT solving, such as polynomial calculus (PC) and cutting planes (CP), very little has been known. Inspired by [BN08, BN11], we consider CNF encodings of so-called pebble games played on graphs and the approach of making such pebbling formulas harder by simple syntactic modifications. We use this paradigm of hardness amplification to make progress on the relatively longstanding open question of proving time-space trade-offs for PC and CP. Namely, we exhibit a family of modified pebbling formulas {F

_{n}}_{n}^{∞}such that: • The formulas F_{n}have size Θ(n) and width O(1). • They have proofs in length O(n) in resolution, which generalize to both PC and CP. • Any refutation in CP or PCR (a generalization of PC) in length L and space s must satisfy s log L_{≈}^{>}4√n. A crucial technical ingredient in these results is a new two-player communication complexity lower bound for composed search problems in terms of block sensitivity, a contribution that we believe to be of independent interest.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:31:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 33. Relating proof complexity measures and practical hardness of SAT Järvisalo, M.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt609",{id:"formSmash:items:resultList:32:j_idt609",widgetVar:"widget_formSmash_items_resultList_32_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Matsliah, A.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Živný, S.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Relating proof complexity measures and practical hardness of SAT2012Inngår i: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, s. 316-331Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:32:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_32_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Boolean satisfiability (SAT) solvers have improved enormously in performance over the last 10-15 years and are today an indispensable tool for solving a wide range of computational problems. However, our understanding of what makes SAT instances hard or easy in practice is still quite limited. A recent line of research in proof complexity has studied theoretical complexity measures such as length, width, and space in resolution, which is a proof system closely related to state-of-the-art conflict-driven clause learning (CDCL) SAT solvers. Although it seems like a natural question whether these complexity measures could be relevant for understanding the practical hardness of SAT instances, to date there has been very limited research on such possible connections. This paper sets out on a systematic study of the interconnections between theoretical complexity and practical SAT solver performance. Our main focus is on space complexity in resolution, and we report results from extensive experiments aimed at understanding to what extent this measure is correlated with hardness in practice. Our conclusion from the empirical data is that the resolution space complexity of a formula would seem to be a more fine-grained indicator of whether the formula is hard or easy than the length or width needed in a resolution proof. On the theory side, we prove a separation of general and tree-like resolution space, where the latter has been proposed before as a measure of practical hardness, and also show connections between resolution space and backdoor sets.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:32:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 34. Trade-offs between size and degree in polynomial calculus Lagarde, G.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt609",{id:"formSmash:items:resultList:33:j_idt609",widgetVar:"widget_formSmash_items_resultList_33_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.Sokolov, D.Swernofsky, Jospeh AlexanderKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Trade-offs between size and degree in polynomial calculus2020Inngår i: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2020Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:33:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_33_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Building on [Clegg et al.’96], [Impagliazzo et al.’99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(n log S). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen’16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:33:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 35. CNFgen Lauria, M.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt609",{id:"formSmash:items:resultList:34:j_idt609",widgetVar:"widget_formSmash_items_resultList_34_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Elffers, JanKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.Vinyals, MarcKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); CNFgen: A generator of crafted benchmarks2017Inngår i: 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017, Springer, 2017, Vol. 10491, s. 464-473Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:34:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_34_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We present CNFgen, a generator of combinatorial benchmarks in DIMACS and OPB format. The proof complexity literature is a rich source not only of hard instances but also of instances that are theoretically easy but “extremal” in different ways, and therefore of potential interest in the context of SAT solving. Since most of these formulas appear not to be very well known in the SAT community, however, we propose CNFgen as a resource to make them readily available for solver development and evaluation. Many formulas studied in proof complexity are based on graphs, and CNFgen is also able to generate, parse and do basic manipulation of such objects. Furthermore, it includes a library cnfformula giving access to the functionality of CNFgen to Python programs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:34:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 36. Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases Lauria, M.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt609",{id:"formSmash:items:resultList:35:j_idt609",widgetVar:"widget_formSmash_items_resultList_35_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases2017Inngår i: 32nd Computational Complexity Conference (CCC 2017), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017, Vol. 79, artikkel-id 2Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:35:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_35_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We consider the graph k-colouring problem encoded as a set of polynomial equations in the standard way. We prove that there are bounded-degree graphs that do not have legal k-colourings but for which the polynomial calculus proof system defined in [Clegg et al. 1996, Alekhnovich et al. 2002] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving graph k-colouring using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. 2008, 2009, 2011, 2015] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. 2009] and [Li et al. 2016]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Miksa and Nordström 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:35:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 37. Tight size-degree bounds for sums-of-squares proofs Lauria, Massimo PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt606",{id:"formSmash:items:resultList:36:j_idt606",widgetVar:"widget_formSmash_items_resultList_36_j_idt606",onLabel:"Lauria, Massimo ",offLabel:"Lauria, Massimo ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt609",{id:"formSmash:items:resultList:36:j_idt609",widgetVar:"widget_formSmash_items_resultList_36_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Tight size-degree bounds for sums-of-squares proofs2015Inngår i: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2015, Vol. 33, s. 448-466Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:36:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_36_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size nΩ(d) for values of d = d(n) from constant all the way up to nδ for some universal constant δ. This shows that the nO(d) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in [Krajícek’04] and [Dantchev and Riis’03], and then applying a restriction argument as in [Atserias, Müller, and Oliva’13] and [Atserias, Lauria, and Nordström’14]. This yields a generic method of amplifying SOS degree lower bounds to size lower bounds, and also generalizes the approach in [ALN14] to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:36:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 38. Tight Size-Degree Bounds for Sums-of-Squares Proofs Lauria, Massimoet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_37_j_idt609",{id:"formSmash:items:resultList:37:j_idt609",widgetVar:"widget_formSmash_items_resultList_37_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Tight Size-Degree Bounds for Sums-of-Squares Proofs2017Inngår i: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 26, nr 4, s. 911-948Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_37_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:37:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_37_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size for values of d = d(n) from constant all the way up to for some universal constant . This shows that the running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in Krajiek (Arch Math Log 43(4):427-441, 2004) and Dantchev & Riis (Proceedings of the 17th international workshop on computer science logic (CSL '03), 2003) and then applying a restriction argument as in Atserias et al. (J Symb Log 80(2):450-476, 2015; ACM Trans Comput Log 17:19:1-19:30, 2016). This yields a generic method of amplifying SOS degree lower bounds to size lower bounds and also generalizes the approach used in Atserias et al. (2016) to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:37:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 39. Long Proofs of (Seemingly) Simple Formulas Miksa, Mladen PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt606",{id:"formSmash:items:resultList:38:j_idt606",widgetVar:"widget_formSmash_items_resultList_38_j_idt606",onLabel:"Miksa, Mladen ",offLabel:"Miksa, Mladen ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt609",{id:"formSmash:items:resultList:38:j_idt609",widgetVar:"widget_formSmash_items_resultList_38_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Long Proofs of (Seemingly) Simple Formulas2014Inngår i: THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, s. 121-137Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:38:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_38_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); In 2010, Spence and Van Gelder presented a family of CNF formulas based on combinatorial block designs. They showed empirically that this construction yielded small instances that were orders of magnitude harder for state-of-the-art SAT solvers than other benchmarks of comparable size, but left open the problem of proving theoretical lower bounds. We establish that these formulas are exponentially hard for resolution and even for polynomial calculus, which extends resolution with algebraic reasoning. We also present updated experimental data showing that these formulas are indeed still hard for current CDCL solvers, provided that these solvers do not also reason in terms of cardinality constraints (in which case the formulas can become very easy). Somewhat intriguingly, however, the very hardest instances in practice seem to arise from so-called fixed bandwidth matrices, which are provably easy for resolution and are also simple in practice if the solver is given a hint about the right branching order to use. This would seem to suggest that CDCL with current heuristics does not always search efficiently for short resolution proofs, despite the theoretical results of [Pipatsrisawat and Darwiche 2011] and [Atserias, Fichte, and Thurley 2011].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:38:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 40. A generalized method for proving polynomial calculus degree lower bounds Mikša, Mladen PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt606",{id:"formSmash:items:resultList:39:j_idt606",widgetVar:"widget_formSmash_items_resultList_39_j_idt606",onLabel:"Mikša, Mladen ",offLabel:"Mikša, Mladen ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt609",{id:"formSmash:items:resultList:39:j_idt609",widgetVar:"widget_formSmash_items_resultList_39_j_idt609",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Nordström, JakobKTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A generalized method for proving polynomial calculus degree lower bounds2015Inngår i: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2015, Vol. 33, s. 467-487Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:39:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_39_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. ’99] also on proof size. [Alekhnovich and Razborov’03] established that if the clause-variable incidence graph of a CNF formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further develop the techniques in [AR03] to show that if one can "cluster" clauses and variables in a way that "respects the structure" of the formula in a certain sense, then it is sufficient that the incidence graph of this clustered version is an expander. As a corollary of this, we prove that the functional pigeonhole principle (FPHP) formulas require high PC/PCR degree when restricted to constant-degree expander graphs. This answers an open question in [Razborov’02], and also implies that the standard CNF encoding of the FPHP formulas require exponential proof size in polynomial calculus resolution. Thus, while Onto-FPHP formulas are easy for polynomial calculus, as shown in [Riis’93], both FPHP and Onto-PHP formulas are hard even when restricted to bounded-degree expanders.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:39:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 41. A (Biased) Proof Complexity Survey for SAT Practitioners Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt606",{id:"formSmash:items:resultList:40:j_idt606",widgetVar:"widget_formSmash_items_resultList_40_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A (Biased) Proof Complexity Survey for SAT Practitioners2014Inngår i: THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, s. 1-6Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:40:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_40_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); This talk is intended as a selective survey of proof complexity, focusing on some comparatively weak proof systems that are of particular interest in connection with SAT solving. We will review resolution, polynomial calculus, and cutting planes (related to conflict-driven clause learning, Grobner basis computations, and pseudo-Boolean solvers, respectively) and some proof complexity measures that have been studied for these proof systems. We will also briefly discuss if and how these proof complexity measures could provide insights into SAT solver performance.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:40:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 42. A simplified way of proving trade-off results for resolution Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_41_j_idt606",{id:"formSmash:items:resultList:41:j_idt606",widgetVar:"widget_formSmash_items_resultList_41_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A simplified way of proving trade-off results for resolution2009Inngår i: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 109, nr 18, s. 1030-1035Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_41_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:41:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_41_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We present a greatly simplified proof of the length-space trade-off result for resolution in [P. Hertel, T. Pitassi, Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '07), Oct. 2007, pp. 137-149], and also prove a couple of other theorems in the same vein. We point out two important ingredients needed for our proofs to work, and discuss some possible conclusions. Our key trick is to look at formulas of the type F = G ∧ H, where G and H are over disjoint sets of variables and have very different length-space properties with respect to resolution.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:41:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 43. Narrow proofs may be spacious Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_42_j_idt606",{id:"formSmash:items:resultList:42:j_idt606",widgetVar:"widget_formSmash_items_resultList_42_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Narrow proofs may be spacious: Separating space and width in resolution2006Inngår i: Proc. Annu. ACM Symp. Theory Comput., 2006, s. 507-516Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_42_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:42:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_42_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable CNF formulas. Also, the refutation space of a formula has been proven to be at least as large as the refutation width, but it has been open whether space can be separated from width or the two measures coincide asymptotically. We prove that there is a family of k-CNF formulas for which the refutation width in resolution is constant but the refutation space is non-constant, thus solving a problem mentioned in several previous papers.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:42:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 44. Narrow proofs may be spacious Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt606",{id:"formSmash:items:resultList:43:j_idt606",widgetVar:"widget_formSmash_items_resultList_43_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Narrow proofs may be spacious: Separating space and width in resolution2009Inngår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 39, nr 1, s. 59-121Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:43:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_43_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable conjunctive normal form (CNF) formulas. Also, the minimum refutation space of a formula has been proven to be at least as large as the minimum refutation width, but it has been open whether space can be separated from width or the two measures coincide asymptotically. We prove that there is a family of k-CNF formulas for which the refutation width in resolution is constant but the refutation space is nonconstant, thus solving a problem mentioned in several previous papers.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:43:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 45. On Proof Complexity Lower Bounds and Possible Connections to SAT Solving Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_44_j_idt606",{id:"formSmash:items:resultList:44:j_idt606",widgetVar:"widget_formSmash_items_resultList_44_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On Proof Complexity Lower Bounds and Possible Connections to SAT Solving2011Konferansepaper (Fagfellevurdert)46. On the Relative Strength of Pebbling and Resolution Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt606",{id:"formSmash:items:resultList:45:j_idt606",widgetVar:"widget_formSmash_items_resultList_45_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Relative Strength of Pebbling and Resolution2012Inngår i: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 13, nr 2, s. 16-Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:45:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_45_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula and then argue that proofs of this formula must inherit (various aspects of) the pebbling properties of the underlying graph. Unfortunately, the reductions used here are not tight. To simulate resolution proofs by pebblings, the full strength of nondeterministic black-white pebbling is needed, whereas resolution is only known to be able to simulate deterministic black pebbling. To obtain strong results, one therefore needs to find specific graph families which either have essentially the same properties for black and black-white pebbling (not at all true in general) or which admit simulations of black-white pebblings in resolution. This article contributes to both these approaches. First, we design a restricted form of black-white pebbling that can be simulated in resolution and show that there are graph families for which such restricted pebblings can be asymptotically better than black pebblings. This proves that, perhaps somewhat unexpectedly, resolution can strictly beat black-only pebbling, and in particular that the space lower bounds on pebbling formulas in Ben-Sasson and Nordstr " om [2008] are tight. Second, we present a versatile parametrized graph family with essentially the same properties for black and black-white pebbling, which gives sharp simultaneous trade-offs for black and black-white pebbling for various parameter settings. Both of our contributions have been instrumental in obtaining the time-space trade-off results for resolution-based proof systems in Ben-Sasson and Nordstr " om [2011].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:45:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 47. On the Relative Strength of Pebbling and Resolution Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt606",{id:"formSmash:items:resultList:46:j_idt606",widgetVar:"widget_formSmash_items_resultList_46_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Massachusetts Institute of Technology.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Relative Strength of Pebbling and Resolution2010Inngår i: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC '10), 2010, s. 151-162Konferansepaper (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:46:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_46_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula and then argue that proofs of this formula must inherit (various aspects of) the pebbling properties of the underlying graph. Unfortunately, the reductions used here are not tight. To simulate resolution proofs by pebblings, the full strength of nondeterministic black-white pebbling is needed, whereas resolution is only known to be able to simulate deterministic black pebbling. To obtain strong results, one therefore needs to find specific graph families which either have essentially the same properties for black and blackwhite pebbling (not at all true in general) or which admit simulations of black-white pebblings in resolution. This paper contributes to both these approaches. First, we design a restricted form of black-white pebbling that can be simulated in resolution and show that there are graph families for which such restricted pebblings can be asymptotically better than black pebblings. This proves that, perhaps somewhat unexpectedly, resolution can strictly beat black-only pebbling, and in particular that the space lower bounds on pebbling formulas in [Ben-Sasson and Nordstr¨om 2008] are tight. Second, we present a versatile parametrized graph family with essentially the same properties for black and black-white pebbling, which gives sharp simultaneous trade-offs for black and black-white pebbling for various parameter settings. Both of our contributions have been instrumental in obtaining the time-space trade-off results for resolution-based proof systems in [Ben-Sasson and Nordstr¨om 2009].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:46:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 48. Pebble games, proof complexity, and time-space trade-offs Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt606",{id:"formSmash:items:resultList:47:j_idt606",widgetVar:"widget_formSmash_items_resultList_47_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Pebble games, proof complexity, and time-space trade-offs2013Inngår i: Logical Methods in Computer Science, E-ISSN 1860-5974, Vol. 9, nr 3, s. 15-Artikkel i tidsskrift (Fagfellevurdert)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:47:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_47_j_idt644_0_j_idt645",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. This is a survey of research in proof complexity drawing on results and tools from pebbling, with a focus on proof space lower bounds and trade-offs between proof size and proof space.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:47:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 49. Short Proofs May Be Spacious Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt606",{id:"formSmash:items:resultList:48:j_idt606",widgetVar:"widget_formSmash_items_resultList_48_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Short Proofs May Be Spacious: Understanding Space in Resolution2008Doktoravhandling, monografi (Annet vitenskapelig)Abstract [sv] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt644_0_j_idt645",{id:"formSmash:items:resultList:48:j_idt644:0:j_idt645",widgetVar:"widget_formSmash_items_resultList_48_j_idt644_0_j_idt645",onLabel:"Abstract [sv]",offLabel:"Abstract [sv]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Om man ser på de bästa nu kända algoritmerna för att avgöra satisfierbarhet hos logiska formler så är de allra flesta baserade på den så kallade DPLL-metoden utökad med klausulinlärning. De två viktigaste gränssättande faktorerna för sådana algoritmer är hur mycket tid och minne de använder, och att förstå sig på detta är därför en fråga som har stor praktisk betydelse.

Inom området beviskomplexitet svarar tids- och minnesåtgång mot längd och minne hos resolutionsbevis för formler i konjunktiv normalform (CNF-formler). En lång rad arbeten har studerat dessa mått och även jämfört dem med bredden av bevis, ett annat mått som visat sig höra nära samman med både längd och minne. Mer formellt är längden hos ett bevis antalet rader, dvs. klausuler, bredden är storleken av den största klausulen, och minnet är maximala antalet klausuler som man behöver komma ihåg samtidigt om man under bevisets gång bara får dra nya slutsatser från klausuler som finns sparade.

För längd och bredd har man lyckats visa en rad starka resultat men förståelsen av måttet minne har lämnat mycket i övrigt att önska. Till exempel så är det känt att minnet som behövs för att bevisa en formel är minst lika stort som den nödvändiga bredden, men det har varit en öppen fråga om minne och bredd kan separeras eller om de två måtten mäter "samma sak" i den meningen att de alltid är asymptotiskt lika stora för en formel. Det har också varit okänt om det faktum att det finns ett kort bevis för en formel medför att formeln också kan bevisas i litet minne (motsvarande påstående är sant för längd jämfört med bredd) eller om det tvärtom kan vara så att längd och minne är "helt orelaterade" på så sätt att även korta bevis kan kräva maximal mängd minne.

I denna avhandling presenterar vi först ett förenklat bevis av trade-off-resultatet för längd jämfört med minne i (Hertel och Pitassi 2007) och visar hur samma idéer kan användas för att visa ett par andra exponentiella avvägningar i relationerna mellan olika beviskomplexitetsmått för resolution.

Sedan visar vi att det finns formler som kan bevisas i linjär längd och konstant bredd men som kräver en mängd minne som växer logaritmiskt i formelstorleken, vilket vi senare förbättrar till kvadratroten av formelstorleken. Dessa resultat separerar således minne och bredd. Genom att använda andra men besläktade idéer besvarar vi därefter frågan om hur minne och längd förhåller sig till varandra genom att separera dem på starkast möjliga sätt. Mer precist visar vi att det finns CNF-formler av storlek O(n) som har resolutionbevis i längd O(n) och bredd O(1) men som kräver minne minst Omega(n/log n). Det gemensamma temat för dessa resultat är att vi studerar formler som beskriver stenläggningsspel, eller pebblingspel, på riktade acykliska grafer. Vi bevisar undre gränser för det minne som behövs för den så kallade pebblingformeln över en graf uttryckt i det svart-vita pebblingpriset för grafen i fråga.

Slutligen observerar vi att vår optimala separation av minne och längd i själva verket är ett specialfall av en mer generell sats. Låt F vara en CNF-formel och f:{0,1}^d->{0,1} en boolesk funktion. Ersätt varje variabel x i F med f(x_1, ..., x_d) och skriv om denna nya formel på naturligt sätt som en CNF-formel F[f]. Då gäller, givet att F och f har rätt egenskaper, att F[f] kan bevisas i resolution i väsentligen samma längd och bredd som F, men att den minimala mängd minne som behövs för F[f] är åtminstone lika stor som det minimala antalet variabler som måste förekomma samtidigt i ett bevis för F.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:48:j_idt644:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Fulltekst (pdf)FULLTEXT01$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_items_resultList_48_j_idt869_0_j_idt872",{id:"formSmash:items:resultList:48:j_idt869:0:j_idt872",widgetVar:"widget_formSmash_items_resultList_48_j_idt869_0_j_idt872",showEffect:"fade",hideEffect:"fade",target:"formSmash:items:resultList:48:j_idt869:0:fullText"});}); 50. Understanding the Hardness of Proving Formulas in Propositional Logic Nordström, Jakob PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt606",{id:"formSmash:items:resultList:49:j_idt606",widgetVar:"widget_formSmash_items_resultList_49_j_idt606",onLabel:"Nordström, Jakob ",offLabel:"Nordström, Jakob ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Understanding the Hardness of Proving Formulas in Propositional Logic2011Konferansepaper (Fagfellevurdert)

RefereraExporteraLink til resultatlisten
http://kth.diva-portal.org/smash/resultList.jsf?query=&language=no&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A31369+OR+0000-0002-2700-4285%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_lower_j_idt926_recordPermLink",{id:"formSmash:lower:j_idt926:recordPermLink",widgetVar:"widget_formSmash_lower_j_idt926_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt926_j_idt928",{id:"formSmash:lower:j_idt926:j_idt928",widgetVar:"widget_formSmash_lower_j_idt926_j_idt928",target:"formSmash:lower:j_idt926:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Referera

Referensformatapa ieee modern-language-association-8th-edition vancouver Annet format $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt944",{id:"formSmash:lower:j_idt944",widgetVar:"widget_formSmash_lower_j_idt944",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt944",e:"change",f:"formSmash",p:"formSmash:lower:j_idt944",u:"formSmash:lower:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association-8th-edition
- vancouver
- Annet format

Språkde-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Annet språk $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt955",{id:"formSmash:lower:j_idt955",widgetVar:"widget_formSmash_lower_j_idt955",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt955",e:"change",f:"formSmash",p:"formSmash:lower:j_idt955",u:"formSmash:lower:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Annet språk

Utmatningsformathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt965",{id:"formSmash:lower:j_idt965",widgetVar:"widget_formSmash_lower_j_idt965"});});

- html
- text
- asciidoc
- rtf