Massimo Lauria

According to our database, Massimo Lauria authored at least 41 papers between 2005 and 2024.

Collaborative distances:

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

2024

Redundancy for MaxSAT.

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

Electron. Colloquium Comput. Complex., 2024

2023

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.

Ilario Bonacina, Nicola Galesi, Massimo Lauria

Comput. Complex., December, 2023

Verification and generation of unrefinable partitions.

Riccardo Aragona, Lorenzo Campioni, Roberto Civino, Massimo Lauria

Inf. Process. Lett., March, 2023

Circular (Yet Sound) Proofs in Propositional Logic.

Albert Atserias, Massimo Lauria

ACM Trans. Comput. Log., 2023

2021

Clique Is Hard on Average for Regular Resolution.

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

J. ACM, 2021

Upper bounds on positional Paris-Harrington games.

Lorenzo Carlucci, Massimo Lauria

Discret. Math., 2021

The Power of Negative Reasoning.

Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov

Proceedings of the 36th Computational Complexity Conference, 2021

2019

Circular (Yet Sound) Proofs.

Albert Atserias, Massimo Lauria

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

2018

On semantic cutting planes with very small coefficients.

Massimo Lauria, Neil Thapen

Inf. Process. Lett., 2018

A note about <i>k</i>-DNF resolution.

Massimo Lauria

Inf. Process. Lett., 2018

Cliques enumeration and tree-like resolution proofs.

Massimo Lauria

Inf. Process. Lett., 2018

Algorithm Analysis Through Proof Complexity.

Massimo Lauria

Proceedings of the Sailing Routes in the World of Computation, 2018

2017

The complexity of proving that a graph is Ramsey.

Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen

Comb., 2017

Tight Size-Degree Bounds for Sums-of-Squares Proofs.

Massimo Lauria, Jakob Nordström

Comput. Complex., 2017

CNFgen: A Generator of Crafted Benchmarks.

Massimo Lauria, Jan Elffers, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28, 2017

Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases.

Massimo Lauria, Jakob Nordström

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem.

Massimo Lauria

ACM Trans. Comput. Theory, 2016

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies.

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2016

Narrow Proofs May Be Maximally Long.

Albert Atserias, Massimo Lauria, Jakob Nordström

ACM Trans. Comput. Log., 2016

Semantic Versus Syntactic Cutting Planes.

Yuval Filmus, Pavel Hrubes, Massimo Lauria

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.

Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

2015

From Small Space to Small Width in Resolution.

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

ACM Trans. Comput. Log., 2015

Hardness of Approximation in PSPACE and Separation Results for Pebble Games.

Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2013

Parameterized Complexity of DPLL Search Procedures.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2013

A characterization of tree-like Resolution size.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Inf. Process. Lett., 2013

Short $\mathsf{Res}^*(\mathsf{polylog})$ refutations if and only if narrow $\mathsf{Res}$ refutations.

Massimo Lauria

CoRR, 2013

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract).

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

A rank lower bound for cutting planes proofs of Ramsey Theorem.

Massimo Lauria

Electron. Colloquium Comput. Complex., 2012

Space Complexity in Polynomial Calculus.

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

Electron. Colloquium Comput. Complex., 2012

2010

Optimality of size-degree tradeoffs for polynomial calculus.

Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2010

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Inf. Process. Lett., 2010

Paris-Harrington tautologies.

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2010

Parameterized Bounded-Depth Frege is Not Optimal.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2010

Hardness of Parameterized Resolution.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2010

2009

Random CNFs require spacious Polynomial Calculus refutations.

Massimo Lauria

Electron. Colloquium Comput. Complex., 2009

On the Automatizability of Polynomial Calculus.

Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2009

2008

Minimum-Energy Broadcast and disk cover in grid wireless networks.

Tiziana Calamoneri, Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Riccardo Silvestri

Theor. Comput. Sci., 2008

2007

On the bounded-hop MST problem on random Euclidean instances.

Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi, Riccardo Silvestri

Theor. Comput. Sci., 2007

Extending Polynomial Calculus to $k$-DNF Resolution.

Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2007

2006

A Distributed Protocol for the Bounded-Hops Converge-Cast in Ad-Hoc Networks.

Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi, Riccardo Silvestri

Proceedings of the Ad-Hoc, Mobile, and Wireless Networks, 5th International Conference, 2006

2005

Divide and Conquer Is Almost Optimal for the Bounded-Hop MST Problem on Random Euclidean Instances.

Andrea E. F. Clementi, Miriam Di Ianni, Angelo Monti, Massimo Lauria, Gianluca Rossi, Riccardo Silvestri

Proceedings of the Structural Information and Communication Complexity, 2005