MASSIMO LAURIA

Ricevimento per appuntamento, via email: Giovedì 11.00-13.00

(Il ricevimento potrà essere organizzato via Zoom o mezzi analoghi)

# PUBLICATIONS {#publications .unnumbered}

In computer science it is often the case that a paper appears in a
conference with published proceedings first, usually in a reduced form,
and then the corresponding full version appears in a journal. In such
cases here we list both publications.

## PEER REVIEWED INTERNATIONAL JOURNALS {#peer-reviewed-international-journals .unnumbered}

1. (TOCL 2023) Albert Atserias and **Massimo Lauria**. *Circular (Yet
Sound) Proofs in Propositional Logic* In ACM Transaction on
Computational Logic. (Conference version appeared in SAT 2019 with
the name "Circular (Yet Sound) Proofs")\

2. (IPL 2023) Riccardo Aragona, Lorenzo Campioni, Roberto Civino and
**Massimo Lauria**. *Verification and generation of unrefinable
partitions* Information Processing Letters 181.\

3. (AE 2022) Riccardo Aragona, Lorenzo Campioni, Roberto Civino and
**Massimo Lauria**. *On the maximal part in unrefinable partitions
of triangular numbers* Aequationes Mathematicae. 96(6):1339--1363.\

4. (JACM 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* Journal of the ACM
68(4), 2021. (Conference version appeared in STOC 2018).\

5. (DM 2021) Lorenzo Carlucci, **Massimo Lauria**. *Upper bounds on
positional Paris--Harrington games* Discrete Mathematics
344:3(2021), pp. 1--6.\

6. (IPL 2018) **Massimo Lauria**. *A note about k-DNF resolution*
Information Processing Letters 137. pp. 33--39.\

7. (IPL 2018) **Massimo Lauria**, Neil Thapen. *On semantic cutting
planes with very small coefficients*. Information Processing Letters
136: pp. 70--75.\

8. (IPL 2018) **Massimo Lauria**. *Cliques enumeration and tree-like
resolution proofs*. Information Processing Letters 135: pp. 62--67.\

9. (Complexity 2017) **Massimo Lauria**, Jakob Nordström. *Tight Size
and Degree Lower Bounds for Sums-Of-Squares Proofs*. Computational
Complexity 26(4):911--948. (Conference version appeared in CCC
2015).\

10. (Combinatorica 2017) **Massimo Lauria**, Pavel Pudlák, Vojtěch Rödl
and Neil Thapen. *The Complexity of Proving that a Graph is Ramsey*.
Combinatorica vol. 37: pp. 253-268. (Conference version appeared in
ICALP 2013).\

11. (ToCL 2016) Lorenzo Carlucci, Nicola Galesi, **Massimo Lauria**. *On
the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey
Tautologies*. ACM Transaction on Computational Logic
17(4):26:1--26:25. (Conference version appeared in CCC 2011 with the
name "Paris-Harrington Tautologies")\

12. (ToCT 2016) **Massimo Lauria**. *A rank lower bound for cutting
planes proofs of Ramsey Theorem*. ACM Transaction on Computational
Theory 8(4):17:1--17:13. (Conference version appeared in SAT 2013).\

13. (ToCL 2016) Albert Atserias, **Massimo Lauria**, Jakob Nordström.
*Narrow Proofs May Be Maximally Long*. ACM Transaction on
Computational Logic 17(3):19:1--19:30. (Conference version appeared
in CCC 2014).\

14. (ToCL 2015) Yuval Filmus, **Massimo Lauria**, Mladen Mikša, Jakob
Nordström, Marc Vinyals. *From Small Space to Small Width in
Resolution*. ACM Transaction on Computational Logic
16(4):28:1--28:15. (Conference version appeared in STACS 2014).\

15. (SICOMP 2015) Yuval Filmus, **Massimo Lauria**, Jakob Nordström,
Noga Ron-Zewi, Neil Thapen. *Space Complexity in Polynomial
Calculus*. SIAM Journal of Computing, 44(4), 1119--1153. (Conference
version appeared in CCC 2012).\

16. (ToCL 2013) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**.
*Parameterized Complexity of DPLL Search Procedures*. ACM
Transaction on Computational Logic 14:20:1--20:21. (Conference
version appeared in SAT 2011).\

17. (IPL 2013) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**. *A
Characterization of Tree-Like Resolution Size*. Information
Processing Letters 113(18): pp. 666--671.\

18. (ToCT 2012) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**,
Alexander A. Razborov. *Parameterized Bounded-depth Frege is not
optimal*. ACM Transaction on Computational Theory 4:7:1--7:16.
(Conference version appeared in ICALP 2011).\

The paper has been selected in "Computing Reviews' Notable Books and
Articles 2012 list" (See
)

19. (IPL 2010) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**. *A
lower bound for the pigeonhole principle in tree-like Resolution by
asymmetric Prover--Delayer games*. Information Processing Letters
110(23): pp. 1074--1077.\

20. (ToCL 2010) Nicola Galesi, **Massimo Lauria**. *Optimality of
size-degree trade-offs for Polynomila Calculus*. ACM Transaction on
Computational Logic 12:4:1--4:22, November 2010.

21. (ToCSys 2010) Nicola Galesi, **Massimo Lauria**. *On the
Automatizability of Polynomial Calculus*. Theory of Computing
Systems 47(20):491--506.\

22. (TCS 2008) 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*.
Theoretical Computer Science 399(1--2): 38--53, 2008. (Conference
version appeared in SIROCCO 2006).\

23. (TCS 2007) 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*. Theoretical
Computer Science 384(2--3): 161--167, 2007. (Conference version
appeared in SIROCCO 2005 with the title "Divide and conquer is
almost optimal for the bounded-hop MST problem on random euclidean
instances").\

## PEER REVIEWED INTERNATIONAL CONFERENCES WITH PROCEEDINGS {#peer-reviewed-international-conferences-with-proceedings .unnumbered}

1. (MFCS 2022) Ilario Bonacina, Nicola Galesi and **Massimo Lauria**.
*On vanishing sums of roots of unity in polynomial calculus and
sum-of-squares* In: 47th International Symposium on Mathematical
Foundations of Computer Science (MFCS 2022). pp. 23:1--23:15.\

2. (CCC 2021) Susanna F. de Rezende, **Massimo Lauria**, Jakob
Nordström and Dmitry Sokolov. *The power of negative reasoning* In
Proc. of 36th Computational Complexity Conference (CCC 2021), pp.
40:1--40:24.\

3. (SAT 2019) Albert Atserias and **Massimo Lauria**. *Circular (Yet
Sound) Resolution* In Proc. of 22nd International Conference on
Theory and Applications of Satisfiability Testing (SAT 2019).
Lecture Notes in Computer Science vol. 101628, pp. 1--18.\

4. (STOC 2018) Albert Atserias, Ilario Bonacina, Susanna F. de Rezende,
**Massimo Lauria**, Jakob Nordström and Alexander A. Razborov.
*Clique Is Hard on Average for Regular Resolution* In Proc. of 50th
ACM Symposium on Theory of Computing (STOC 2018), pp. 866--877.\

5. (CiE 2018) **Massimo Lauria**. *Algorithm Analysis Through Proof
Complexity* In Proc. of the 14th Conference on Computability in
Europe (CiE 2018). Lecture Notes in Computer Science vol. 10936, pp.
254--263.\

6. (CCC 2017) **Massimo Lauria** and Jakob Nordström. *Graph Colouring
is Hard for Algorithms Based on Hilbert's Nullstellensatz and
Gröbner Bases*. In Proc. of 32nd Computational Complexity Conference
(CCC 2017). LIPIcs. vol. 79, pp. 2:1--2:20.\

7. (SAT 2017) **Massimo Lauria**, Jan Elffers, Jakob Nordström, Marc
Vinyals *CNFgen: A generator of crafted benchmarks* In Proc. of The
19th International Conference on Theory and Applications of
Satisfiability Testing (SAT 2017). Lecture Notes in Computer Science
vol. 10491, pp. 464-473.\

8. (SAT 2016) Jan Elffers, Jan Johannsen, **Massimo Lauria**, Thomas
Magnard, Jakob Nordstrom and Marc Vinyals. *Trade-offs Between Time
and Memory in a Tighter Model of CDCL*. In Proc. of The 19th
International Conference on Theory and Applications of
Satisfiability Testing (SAT 2016). Lecture Notes in Computer Science
vol. 9710, pp. 160--176.\

9. (STACS 2016) Yuval Filmus, Pavel Hrubes, **Massimo Lauria**.
*Semantic versus syntactic cutting planes*. In Proc. of The 33rd
International Symposium on Theoretical Aspects of Computer Science
(STACS 2016). LIPIcs. vol. 47, pp. 35:1--35:13.\

10. (CCC 2015) **Massimo Lauria**, Jakob Nordström. *Tight Size and
Degree Lower Bounds for Sums-Of-Squares Proofs*. In Proc. of 30th
Conference on Computational Complexity (CCC 2015). LIPIcs. vol. 33,
pp. 448--466. (Journal version appeared in Computational Complexity
vol. 26)\

11. (FOCS 2015) Siu Man Chan, **Massimo Lauria**, Jakob Nordström, Marc
Vinyals. *Hardness of Approximation in PSPACE and Separation Results
for Pebble Games*. In Proc. of 56th Annual IEEE Symposium on
Foundations of Computer Science (FOCS 2015), pp. 466--485.\

12. (CCC 2014) Albert Atserias, **Massimo Lauria**, Jakob Nordström.
*Narrow Proofs May Be Maximally Long*. In. Proc of the IEEE 29th
Conference on Computational Complexity (CCC 2014), pp. 286--297.
(Journal version appeared in ACM Transaction on Computational Logic,
vol. 17)\

13. (STACS 2014) Yuval Filmus, **Massimo Lauria**, Mladen Mikša, Jakob
Nordström, Marc Vinyals. *From Small Space to Small Width in
Resolution*. In Proc. of 31st International Symposium on Theoretical
Aspects of Computer Science (STACS 2014). LIPIcs. vol. 25, pp.
300--311. (Journal version appeared in ACM Transaction on
Computational Logic, vol. 16).\

14. (SAT 2013) **Massimo Lauria**. *A rank lower bound for cutting
planes proofs of Ramsey Theorem*. In Proc. of the 16th International
Conference on Theory and Applications of Satisfiability Testing (SAT
2013). Lecture Notes in Computer Science vol. 7962, p. 351--364.
(Journal version appeared in ACM Transaction on Computational
Theory, vol. 8).\

15. (ICALP 2013) **Massimo Lauria**, Pavel Pudlák, Vojtěch Rödl and Neil
Thapen. *The Complexity of Proving that a Graph is Ramsey*. In Proc.
of 40th International Colloquium on Automata, Languages, and
Programming (ICALP 2013). Lecture Notes in Computer Science vol.
7965, pp. 684--695. (Journal version appeared in Combinatorica, vol.
37).\

16. (ICALP 2013) Yuval Filmus, **Massimo Lauria**, Mladen Mikša, Jakob
Nordström, Marc Vinyals. *Towards an Understanding of Polynomial
Calculus: New Separations and Lower Bounds (Extended Abstract)*. In
Proc. of International Colloquium on Automata , Languages and
Programming (ICALP 2013). Lecture Notes in Computer Science vol.
7965, pp. 437--448.\

17. (CCC 2012) Yuval Filmus, **Massimo Lauria**, Jakob Nordström, Neil
Thapen, Noga Ron-Zewi. *Space Complexity in Polynomial Calculus*. In
Proc. of the 27th IEEE Conference on Computational Complexity (CCC
2012), pp. 334--344. (Journal version appeared in SIAM Journal of
Computing, vol. 44).\

18. (CCC 2011) Lorenzo Carlucci, Nicola Galesi, **Massimo Lauria**.
*Paris-Harrington Tautologies*. In Proc. of the 26th IEEE Conference
on Computational Complexity (CCC 2011), pp. 93--103. (Journal
version appeared in ACM Transaction on Computational Logic, vol.
17).\

19. (ICALP 2011) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**,
Alexander A. Razborov. *Parameterized Bounded-depth Frege is not
optimal*. In Proc. of the 38th International Colloquium on Automata,
Languages and Programming (ICALP 2011) Lecture Notes in Computer
Science vol. 6755, pp. 630--641. (Journal version appeared in ACM
Transaction on Computational Theory, vol. 4)

20. (SAT 2011) Olaf Beyersdorff, Nicola Galesi, **Massimo Lauria**.
*Parameterized Complexity of DPLL Search Procedures*. In Proc. the
14th International Conference of Theory and Applications of
Satisfiability Testing (SAT 2011). Lecture Notes in Computer Science
vol. 6695, pp. 5--18. (Journal version appeared in ACM Transaction
on Computational Logic, vol. 14).\

21. (AdHocNOW 2006) Andrea E. F. Clementi, Miriam Di Ianni, **Massimo
Lauria**, Gianluca Rossi, Angelo Monti, Riccardo Silvestri. *A
Distributed Protocol for the Bounded-Hops Converge-casr in Ad-Hoc
Networks*. In Proc. of the 5th International Conference on Ad-Hoc,
Mobile, and Wireless Networks, (ADHOC-NOW 2006). Lecture Notes in
Computer Science vol. 4104, pp. 60--72.\

22. (Sirocco 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*.
Lecture Notes in Computer Science vol. 4056, pp. 227--239. (Journal
version appeared in Theoretical Computer Science, vol. 399).\

23. (Sirocco 2005) Andrea E. F. Clementi, Miriam Di Ianni, **Massimo
Lauria**, Angelo Monti, Gianluca Rossi, Riccardo Silvestri. *Divide
and conquer is almost optimal for the bounded-hop MST problem on
random euclidean instances*. In Proc. of the 12th International
Colloquium on Structural Information and Communication Complexity
(SIROCCO 2005). Lecture Notes in Computer Science vol. 3499, pp.
89--98. (Journal version appeared in Theoretical Computer Science,
vol. 384, with title "On the bounded-hop MST problem on random
Euclidean instances").\