Ilario Bonacina

According to our database, Ilario Bonacina authored at least 27 papers between 2013 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2025

Strength and limitations of Sherali-Adams and Nullstellensatz proof systems.

Ilario Bonacina, Maria Luisa Bonet

Ann. Pure Appl. Log., 2025

An Algebraic Approach to MaxCSP.

Ilario Bonacina, Jordi Levy

Proceedings of the 28th International Conference on Theory and Applications of Satisfiability Testing, 2025

Redundancy Rules for MaxSAT.

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

Proceedings of the 28th International Conference on Theory and Applications of Satisfiability Testing, 2025

Semi-Algebraic Proof Systems for QBF.

Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann

Proceedings of the 28th International Conference on Theory and Applications of Satisfiability Testing, 2025

2024

Weighted, Circular and Semi-Algebraic Proofs.

Ilario Bonacina, Maria Luisa Bonet, Jordi Levy

J. Artif. Intell. Res., 2024

Redundancy for MaxSAT.

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

Electron. Colloquium Comput. Complex., 2024

Polynomial calculus for optimization.

Ilario Bonacina, Maria Luisa Bonet, Jordi Levy

Artif. Intell., 2024

MaxSAT Resolution with Inclusion Redundancy.

Ilario Bonacina, Maria Luisa Bonet, Massimo Lauria

Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing, 2024

Weighted, Circular and Semi-Algebraic Proofs (Abstract Reprint).

Ilario Bonacina, Maria Luisa Bonet, Jordi Levy

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

2023

Polynomial Calculus for MaxSAT.

Ilario Bonacina, Maria Luisa Bonet, Jordi Levy

Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing, 2023

2022

A separation of PLS from PPP.

Ilario Bonacina, Neil Thapen

Electron. Colloquium Comput. Complex., 2022

On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares.

Ilario Bonacina, Nicola Galesi, Massimo Lauria

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems.

Ilario Bonacina, Maria Luisa Bonet

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

2020

Frege Systems for Quantified Boolean Logic.

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, Ján Pich

J. ACM, 2020

2018

Clique is hard on average for regular resolution.

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Space proof complexity for random 3-CNFs.

Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan

Inf. Comput., 2017

Space in Weak Propositional Proof Systems

Ilario Bonacina

Springer, ISBN: 978-3-319-73452-1, 2017

2016

Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis.

Ilario Bonacina, Navid Talebanfard

Inf. Process. Lett., 2016

Space in weak propositional proof systems.

Ilario Bonacina

Bull. EATCS, 2016

Lower Bounds: From Circuits to QBF Proof Systems.

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Total Space in Resolution Is at Least Width Squared.

Ilario Bonacina

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

A Framework for Space Complexity in Algebraic Proof Systems.

Ilario Bonacina, Nicola Galesi

J. ACM, 2015

Strong ETH and Resolution via Games and the Multiplicity of Strategies.

Ilario Bonacina, Navid Talebanfard

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2014

Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem.

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

Electron. Colloquium Comput. Complex., 2014

Proofs of Space: When Space Is of the Essence.

Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, Nicola Galesi

Proceedings of the Security and Cryptography for Networks - 9th International Conference, 2014

Total Space in Resolution.

Ilario Bonacina, Nicola Galesi, Neil Thapen

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems.

Ilario Bonacina, Nicola Galesi

Proceedings of the Innovations in Theoretical Computer Science, 2013