This section lists only works not yet published in conferences or journals and hence not peer-rewieved .

For older preprints you might look at dblp or ECCC.

Notes of more expository nature are in the Teaching section.

Go to top ⇧

Journal Articles

[1]Bennett, P., Bonacina, I., Galesi, N., Huynh, T., Molloy, M. and Wollan, P. 2017. Space proof complexity for random 3-CNFs. Information and Computation. 255, (2017), 165–176. ⇨ doi

[2]Bonacina, I. and Talebanfard, N. 2016. Strong ETH and Resolution via Games and the Multiplicity of Strategies. Algorithmica. (Oct. 2016), 1–13. ⇨ doi

[3]Bonacina, I., Galesi, N. and Thapen, N. 2016. Total Space in Resolution. SIAM J. Comput. 45, 5 (Jan. 2016), 1894–1909. ⇨ doi

[4]Bonacina, I. and Talebanfard, N. 2016. Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis. Inf. Process. Lett. 116, 2 (2016), 120–124. ⇨ doi

[5]Bonacina, I. and Galesi, N. 2015. A Framework for Space Complexity in Algebraic Proof Systems. J. ACM. 62, 3 (Jun. 2015), 1–20. ⇨ doi

Go to top ⇧

Conference Articles

[1]Atserias, A., Bonacina, I., De Rezende, S., Lauria, M., Nordström, J. and Razborov, A. 2018. Clique Is Hard on Average for Regular Resolution. to appear in 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC’ 18) (2018). ⇨ doi

[2]Bonacina, I. 2016. Total Space in Resolution is at Least Width Squared. 43rd International Colloquium on Automata, Languages, and Programming – ICALP (2016), 56:1–56:13. ⇨ doi

[3]Beyersdorff, O., Bonacina, I. and Leroy, C. 2016. Lower Bounds: From Circuits to QBF Proof Systems. 7th Conf. Innov. Theor. Comput. Sci. – ITCS (2016), 249–260. ⇨ doi

[4]Bonacina, I. and Talebanfard, N. 2015. Strong ETH and Resolution via Games and the Multiplicity of Strategies. 10th International Symposium on Parameterized and Exact Computation – IPEC (2015), 248–257. ⇨ doi

[5]Bonacina, I., Galesi, N. and Thapen, N. 2014. Total Space in Resolution. 55th Annu. Symp. Found. Comput. Sci. – FOCS (Oct. 2014), 641–650. ⇨ doi

[6]Ateniese, G., Bonacina, I., Faonio, A. and Galesi, N. 2014. Proofs of Space: When Space Is of the Essence. Security and Cryptography for Networks - 9th International Conference – SCN (2014), 538–557. ⇨ doi

[7]Bonacina, I. and Galesi, N. 2013. Pseudo-partitions, transversality and locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. 4th Conf. Innov. Theor. Comput. Sci. – ITCS (2013), 455–472. ⇨ doi

Go to top ⇧

Space in weak propositional proof systems

PhD thesis

[1]Bonacina, I. 2015. Space in weak propositional proof systems. Sapienza University of Rome. ⇨ doi

This thesis was awarded “Best Italian PhD Thesis in Theoretical Computer Science” for the year 2016 by the Italian chapter of the EATCS. It was published with Springer in January 2018.

Go to top ⇧


Here is the list of my co-authors: Giuseppe Ateniese; Olaf Beyersdorff; Patrick Bennett; Leroy Chew; Susanna F. de Rezende; Antonio Faonio; Nicola Galesi; Tony Huynh; Massimo Lauria; Jakob Nordström; Mike Molloy; Alexander Razborov; Navid Talebanfard; Neil Thapen; Paul Wollan.

© Copyright disclaimer The documents contained in this page are included to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.