Below there is a list of my publications. Other entities listing some of my works include dblp or ECCC for instance.

Journals

Bonacina, I., & Talebanfard, N. (2016). Strong ETH and Resolution via Games and the Multiplicity of Strategies. Algorithmica, 1–13.
@article{BT16-algorithmica,
  author = {Bonacina, Ilario and Talebanfard, Navid},
  title = {Strong ETH and Resolution via Games and the Multiplicity of Strategies},
  journal = {Algorithmica},
  pages = {1--13},
  year = {2016},
  month = oct,
  doi = {10.1007/s00453-016-0228-6}
}

Bonacina, I., Galesi, N., & Thapen, N. (2016). Total Space in Resolution. SIAM J. Comput., 45(5), 1894–1909.
@article{BGT16-siamjcomp,
  author = {Bonacina, Ilario and Galesi, Nicola and Thapen, Neil},
  title = {{Total Space in Resolution}},
  journal = {SIAM J. Comput.},
  volume = {45},
  number = {5},
  pages = {1894--1909},
  month = jan,
  year = {2016},
  doi = {10.1137/15M1023269}
}

Bonacina, I., & Talebanfard, N. (2016). Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis. Inf. Process. Lett., 116(2), 120–124.
@article{BT16-ipl,
  author = {Bonacina, Ilario and Talebanfard, Navid},
  title = {{Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis}},
  journal = {Inf. Process. Lett.},
  volume = {116},
  number = {2},
  pages = {120--124},
  year = {2016},
  doi = {10.1016/j.ipl.2015.09.013}
}

Bonacina, I., & Galesi, N. (2015). A Framework for Space Complexity in Algebraic Proof Systems. J. ACM, 62(3), 1–20.
@article{BG15-jacm,
  author = {Bonacina, Ilario and Galesi, Nicola},
  title = {{A Framework for Space Complexity in Algebraic Proof Systems}},
  journal = {J. ACM},
  volume = {62},
  number = {3},
  pages = {1--20},
  year = {2015},
  month = jun,
  doi = {10.1145/2699438}
}

Go to top

Conferences

Bonacina, I. (2016). Total Space in Resolution is at Least Width Squared. In 43rd International Colloquium on Automata, Languages, and Programming – ICALP (Vol. 55, pp. 56:1–56:13).
@inproceedings{Bon16-icalp,
  author = {Bonacina, Ilario},
  title = {{Total Space in Resolution is at Least Width Squared}},
  booktitle = {43rd International Colloquium on Automata, Languages, and Programming -- ICALP},
  pages = {56:1--56:13},
  year = {2016},
  volume = {55},
  doi = {10.4230/LIPIcs.ICALP.2016.56}
}

Beyersdorff, O., Bonacina, I., & Leroy, C. (2016). Lower Bounds: From Circuits to QBF Proof Systems. In 7th Conf. Innov. Theor. Comput. Sci. – ITCS (pp. 249–260).
@inproceedings{BBC16-itcs,
  author = {Beyersdorff, Olaf and Bonacina, Ilario and Leroy, Chew},
  title = {{Lower Bounds: From Circuits to QBF Proof Systems}},
  booktitle = {7th Conf. Innov. Theor. Comput. Sci. -- ITCS},
  pages = {249--260},
  year = {2016},
  doi = {10.1145/2840728.2840740}
}

Bonacina, I., & Talebanfard, N. (2015). Strong ETH and Resolution via Games and the Multiplicity of Strategies. In 10th International Symposium on Parameterized and Exact Computation – IPEC (pp. 248–257).
@inproceedings{BT15-ipec,
  author = {Bonacina, Ilario and Talebanfard, Navid},
  title = {{Strong ETH and Resolution via Games and the Multiplicity of Strategies}},
  booktitle = {10th International Symposium on Parameterized and Exact Computation -- IPEC},
  pages = {248--257},
  year = {2015},
  doi = {10.4230/LIPIcs.IPEC.2015.248}
}

Bonacina, I., Galesi, N., & Thapen, N. (2014). Total Space in Resolution. In 55th Annu. Symp. Found. Comput. Sci. – FOCS (Vol. 38, pp. 641–650).
@inproceedings{BGT14-focs,
  author = {Bonacina, Ilario and Galesi, Nicola and Thapen, Neil},
  title = {{Total Space in Resolution}},
  booktitle = {55th Annu. Symp. Found. Comput. Sci. -- FOCS},
  pages = {641--650},
  volume = {38},
  year = {2014},
  month = oct,
  doi = {10.1109/FOCS.2014.74}
}

Ateniese, G., Bonacina, I., Faonio, A., & Galesi, N. (2014). Proofs of Space: When Space Is of the Essence. In Security and Cryptography for Networks - 9th International Conference – SCN (pp. 538–557).
@inproceedings{ABFG14-scn,
  author = {Ateniese, Giuseppe and Bonacina, Ilario and Faonio, Antonio and Galesi, Nicola},
  title = {Proofs of Space: When Space Is of the Essence},
  booktitle = {Security and Cryptography for Networks - 9th International Conference -- SCN},
  pages = {538--557},
  year = {2014},
  doi = {10.1007/978-3-319-10879-7_31}
}

Bonacina, I., & Galesi, N. (2013). Pseudo-partitions, transversality and locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. In 4th Conf. Innov. Theor. Comput. Sci. – ITCS (pp. 455–472).
@inproceedings{BG13-itcs,
  author = {Bonacina, Ilario and Galesi, Nicola},
  title = {{Pseudo-partitions, transversality and locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems}},
  booktitle = {4th Conf. Innov. Theor. Comput. Sci. -- ITCS},
  pages = {455--472},
  year = {2013},
  doi = {10.1145/2422436.2422486}
}

Go to top

Manuscripts (not peer-reviewed)

(preprint) Bennett, P., Bonacina, I., Galesi, N., Huynh, T., Molloy, M., & Wollan, P. (2015). Space proof complexity for random 3-CNFs. CoRR, abs/1503.01613.
@article{BBGHMW15-preprint,
  author = {Bennett, Patrick and Bonacina, Ilario and Galesi, Nicola and Huynh, Tony and Molloy, Mike and Wollan, Paul},
  title = {Space proof complexity for random 3-CNFs},
  journal = {CoRR},
  volume = {abs/1503.01613},
  year = {2015}
}

Go to top

PhD thesis

Bonacina, Ilario, "Space in weak propositional proof systems", Sapienza University of Rome, dec 2015.
@phdthesis{Bonacina-phdthesis,
  author = {Bonacina, Ilario},
  title = {Space in weak propositional proof systems},
  school = {Sapienza University of Rome},
  year = {2015},
  month = dec
}

Go to top

Co-authors

Here is a list of my co-authors: Giuseppe Ateniese; Olaf Beyersdorff; Patrick Bennett; Leroy Chew; Antonio Faonio; Nicola Galesi; Tony Huynh; Mike Molloy; 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.