Massimo Lauria

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 30

Top Topics

Space Complexity

Graph Colouring

Top Venues

Electron. Colloquium Comput. Complex.

Inf. Process. Lett.

Publications

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria
Redundancy for MaxSAT. Electron. Colloquium Comput. Complex. (2024)
Ilario Bonacina, Maria Luisa Bonet, Massimo Lauria
MaxSAT Resolution with Inclusion Redundancy. SAT (2024)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs in Propositional Logic. ACM Trans. Comput. Log. 24 (3) (2023)
Ilario Bonacina, Nicola Galesi, Massimo Lauria
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares. Comput. Complex. 32 (2) (2023)
Riccardo Aragona, Lorenzo Campioni, Roberto Civino, Massimo Lauria
Verification and generation of unrefinable partitions. Inf. Process. Lett. 181 (2023)
Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. CoRR (2023)
Massimo Lauria, Jakob Nordström
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. CoRR (2023)
Ilario Bonacina, Nicola Galesi, Massimo Lauria
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares. MFCS (2022)
Ilario Bonacina, Nicola Galesi, Massimo Lauria
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares. Electron. Colloquium Comput. Complex. (2022)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. J. ACM 68 (4) (2021)
Riccardo Aragona, Lorenzo Campioni, Roberto Civino, Massimo Lauria
Verification and generation of unrefinable partitions. CoRR (2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov
The Power of Negative Reasoning. Computational Complexity Conference (2021)
Lorenzo Carlucci, Massimo Lauria
Upper bounds on positional Paris-Harrington games. Discret. Math. 344 (3) (2021)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. CoRR (2020)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs. SAT (2019)
Massimo Lauria
Cliques enumeration and tree-like resolution proofs. Inf. Process. Lett. 135 (2018)
Massimo Lauria, Neil Thapen
On semantic cutting planes with very small coefficients. Inf. Process. Lett. 136 (2018)
Massimo Lauria
-DNF resolution. Inf. Process. Lett. 137 (2018)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique is hard on average for regular resolution. STOC (2018)
Massimo Lauria
Algorithm Analysis Through Proof Complexity. CiE (2018)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs. CoRR (2018)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey. Comb. 37 (2) (2017)
Massimo Lauria, Jan Elffers, Jakob Nordström, Marc Vinyals
CNFgen: A Generator of Crafted Benchmarks. SAT (2017)
Massimo Lauria, Jakob Nordström
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. Computational Complexity Conference (2017)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Comput. Complex. 26 (4) (2017)
Yuval Filmus, Pavel Hrubes, Massimo Lauria
Semantic Versus Syntactic Cutting Planes. STACS (2016)
Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals
Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. SAT (2016)
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies. ACM Trans. Comput. Log. 17 (4) (2016)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log. 17 (3) (2016)
Massimo Lauria
A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem. ACM Trans. Comput. Theory 8 (4) (2016)
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen
Space Complexity in Polynomial Calculus. SIAM J. Comput. 44 (4) (2015)
Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. FOCS (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Computational Complexity Conference (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Electron. Colloquium Comput. Complex. 22 (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. CoRR (2015)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. ACM Trans. Comput. Log. 16 (4) (2015)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. CoRR (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. Electron. Colloquium Comput. Complex. 21 (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. STACS (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Computational Complexity Conference (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. CoRR (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Electron. Colloquium Comput. Complex. 21 (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract). ICALP (1) (2013)
Massimo Lauria
A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem. SAT (2013)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Parameterized Complexity of DPLL Search Procedures. ACM Trans. Comput. Log. 14 (3) (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The Complexity of Proving That a Graph Is Ramsey. ICALP (1) (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey. Electron. Colloquium Comput. Complex. 20 (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey CoRR (2013)
Massimo Lauria
Short $\mathsf{Res}^*(\mathsf{polylog})$ refutations if and only if narrow $\mathsf{Res}$ refutations. CoRR (2013)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
A characterization of tree-like Resolution size. Inf. Process. Lett. 113 (18) (2013)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
A Characterization of Tree-Like Resolution Size. Electron. Colloquium Comput. Complex. 19 (2012)
Massimo Lauria
A rank lower bound for cutting planes proofs of Ramsey Theorem. Electron. Colloquium Comput. Complex. 19 (2012)
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen
Space Complexity in Polynomial Calculus. Electron. Colloquium Comput. Complex. 19 (2012)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege Is not Optimal. ACM Trans. Comput. Theory 4 (3) (2012)
Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi
Space Complexity in Polynomial Calculus. Computational Complexity Conference (2012)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Parameterized Complexity of DPLL Search Procedures. SAT (2011)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) (2011)
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
Paris-Harrington Tautologies. Computational Complexity Conference (2011)
Nicola Galesi, Massimo Lauria
On the Automatizability of Polynomial Calculus. Theory Comput. Syst. 47 (2) (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Hardness of Parameterized Resolution. Circuits, Logic, and Games (2010)
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
Paris-Harrington tautologies. Electron. Colloquium Comput. Complex. 17 (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games. Electron. Colloquium Comput. Complex. 17 (2010)
Nicola Galesi, Massimo Lauria
Optimality of size-degree tradeoffs for polynomial calculus. ACM Trans. Comput. Log. 12 (1) (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege is Not Optimal. Electron. Colloquium Comput. Complex. 17 (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games. Inf. Process. Lett. 110 (23) (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Hardness of Parameterized Resolution. Electron. Colloquium Comput. Complex. 17 (2010)
Nicola Galesi, Massimo Lauria
On the Automatizability of Polynomial Calculus. Electron. Colloquium Comput. Complex. 16 (2009)
Massimo Lauria
Random CNFs require spacious Polynomial Calculus refutations. Electron. Colloquium Comput. Complex. 16 (2009)
Tiziana Calamoneri, Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Riccardo Silvestri
Minimum-Energy Broadcast and disk cover in grid wireless networks. Theor. Comput. Sci. 399 (1-2) (2008)
Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi, Riccardo Silvestri
On the bounded-hop MST problem on random Euclidean instances. Theor. Comput. Sci. 384 (2-3) (2007)
Nicola Galesi, Massimo Lauria
Extending Polynomial Calculus to $k$-DNF Resolution. Electron. Colloquium Comput. Complex. 14 (041) (2007)
Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi, Riccardo Silvestri
A Distributed Protocol for the Bounded-Hops Converge-Cast in Ad-Hoc Networks. ADHOC-NOW (2006)
Tiziana Calamoneri, Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Riccardo Silvestri
Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks. SIROCCO (2006)
Andrea E. F. Clementi, Miriam Di Ianni, Angelo Monti, Massimo Lauria, Gianluca Rossi, Riccardo Silvestri
Divide and Conquer Is Almost Optimal for the Bounded-Hop MST Problem on Random Euclidean Instances. SIROCCO (2005)