Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Ilario Bonacina"'
Autor:
Ilario Bonacina, Maria Luisa Bonet
Publikováno v:
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cf6ccf84d7b7ea871abef3b2cf55dbfb
https://doi.org/10.1145/3531130.3533344
https://doi.org/10.1145/3531130.3533344
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de Catalunya (UPC)
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1a71059526abcfaa4d32b866518de6d
https://doi.org/10.1145/3381881
https://doi.org/10.1145/3381881
Autor:
Susanna F. de Rezende, Ilario Bonacina, Jakob Nordström, Massimo Lauria, Albert Atserias, Alexander A. Razborov
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
We prove that for k ≪ 4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4358b5424aed31f07e64de86ce6bc749
http://arxiv.org/abs/2012.09476
http://arxiv.org/abs/2012.09476
Publikováno v:
FOCS
We show quadratic lower bounds on the total space used in resolution refutations of random k-CNFs over n variables, and of the graph pigeonhole principle and the bit pigeonhole principle for n holes. This answers the long-standing open problem of whe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21e230d90389725e4577a3a1ae97baed
https://doi.org/10.1137/15m1023269
https://doi.org/10.1137/15m1023269
Autor:
Ilario Bonacina
This book considers logical proof systems from the point of view of their space complexity. After an introduction to propositional proof complexity the author structures the book into three main parts. Part I contains two chapters on resolution, one
Autor:
Ilario Bonacina
Publikováno v:
Space in Weak Propositional Proof Systems ISBN: 9783319734521
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6bb16b433278997470c511b4964f8188
https://doi.org/10.1007/978-3-319-73453-8_5
https://doi.org/10.1007/978-3-319-73453-8_5
Autor:
Ilario Bonacina
Publikováno v:
Space in Weak Propositional Proof Systems ISBN: 9783319734521
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::791c1c84ffaf6953b120161be02cc2e4
https://doi.org/10.1007/978-3-319-73453-8_1
https://doi.org/10.1007/978-3-319-73453-8_1
Autor:
Ilario Bonacina
Publikováno v:
Space in Weak Propositional Proof Systems ISBN: 9783319734521
We now show some further applications of the general theorems to prove space lower bounds from Chap. 3 and Chap. 4. That is we see how to prove monomial and resolution total space lower bounds for random k-CNF formulas (Sect. 7.2), the pigeonhole pri
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c9271bca32eb5574cf74ab3f69f2af73
https://doi.org/10.1007/978-3-319-73453-8_7
https://doi.org/10.1007/978-3-319-73453-8_7
Autor:
Ilario Bonacina
Publikováno v:
Space in Weak Propositional Proof Systems ISBN: 9783319734521
In this chapter we investigate the space complexity of resolution in particular from the point of view of the total space measure, see Sect. 3.3.We briefly review results about the clause space (Sect. 3.2) and the variable space measures (Sect. 3.4).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e4537f229a93ac62dc3ac5fd30c95cd6
https://doi.org/10.1007/978-3-319-73453-8_3
https://doi.org/10.1007/978-3-319-73453-8_3