Publications


Preprint

  1. I. Bonacina, N. Galesi, M. Lauria. On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  2. S. Dantchev, N. Galesi, A. Ghani. B. Martin. Proof Complexity and the binary encoding of combinatorial principles.

  3. N. Galesi, D Itsykson, A.Riazanov, A. Sofronova. Bounded-depth Frege complexity of Tseitin Formulas for all graphs.

  4. N. Galesi, F. Ranjbar. A note on bounds and on the complexity of node failure identification in networks.

  5. N. Galesi, F. Ranjbar, M. Zito. Vertex-connectivity for node failure identification in Boolean network tomography.


Journal

  1. Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen. Polynomial Calculus Space and Resolution width. Theory of Computing. To appear

  2. Nicola Galesi, Fariba Ranjbar. Tight bounds to localize failure nodes on trees, grids and through embeddings under boolean network tomography. Theoretical Computer Science.

  3. Nicola Galesi, Navid Talebanfard, Jacobo Toràn. Cops-Robber Games and the Resolution of Tseitin Formulas. ACM Transactions on Computation Theory 12(2): 9:1-9:22 (2020).

  4. Patrick Bennet, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan. Space Proof Complexity for random 3-CNFs. Information and Computation 255, pp. 165–176 (2017).

  5. Ilario Bonacina, Nicola Galesi, Neil Thapen. Total Space in Resolution. Siam Journal on Computing. 45(5), pp. 1894–1909 (2016)

  6. Lorenzo Carlucci, Nicola Galesi and Massimo Lauria. On the Proof Complexity of Paris-Harrington and Off-DiagonalRamsey Tautologies. ACM Transactions on Computational Logic. 17(4), pp. 1–25 Sept. 2016.

  7. Ilario Bonacina, Nicola Galesi. A framework for space complexity in algebraic proof systems. Journal of the ACM. 62(3),pp. 1–20 (2015)

  8. Olaf Beyersdorff, Nicola Galesi and Massimo Lauria. A characterization of tree-like Resolution size. Information Processing Letters 113(18), pp. 666–671 (2013)

  9. Olaf Beyersdorff, Nicola Galesi and Massimo Lauria. Parameterized Complexity of DPLL Search Procedure. ACM Transactions on Computational Logic. 14(3). pp. 1–21 2013.

  10. Olaf Beyersdorff, Nicola Galesi and Massimo Lauria, Alezander Razborov. Parameterized Bounded-Depth Frege is not Optimal. ACM Transactions on Computation Theory (TOCT). 4(3), pp. 1–16 2012.

  11. Olaf Beyersdorff, Nicola Galesi and 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 2010

  12. Nicola Galesi, Massimo Lauria. Optimality of size-degree trade-offs for Polynomial Calculus. ACM Transactions on Computational Logic. 12(1). pp. 491–506 2010.

  13. Nicola Galesi, Massimo Lauria. On the Automatizabilty of Polynomial Calculus. Theory of computing Systems 47(2). pp. 491–506. 2011. Errata-Corrige. Correction of two typo.

  14. Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toni Pitassi. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing. 2(1) pp. 65–90, 2006.

  15. Nicola Galesi, Nicola Thapen. Resolution and Pebbling Games. Selected Papers of SAT 05, Lecture Notes in Computer Science 3596, pp. 76–90, 2006.

  16. Nicola Galesi, Oliver Kullmann. Polynomial SAT decision, hypergraph transversals and Hermitian rank. Selected Papers of SAT 04, Lecture Notes in Computer Science 3542, pp. 89–104., 2005.

  17. Juan Luis Esteban, Nicola Galesi, Jochen Messner. On the Complexity of Resolution with Bounded Conjunctions. Theoretical Computer Science. 21(2-3). pp. 347–370 2004.

  18. Eli Ben-Sasson, Nicola Galesi. Space Complexity for Random Formulae in Resolution. Random Structures and Algorithms, 2003. Vol 23(1), pp.92–109. 2003.

  19. Albert Atserias, Nicola Galesi, Pavel Pudlak. Monotone Simulations of nonmonotone Propositional Proofs. Journal of Computer and System Science. 65(4), pp. 626–638 (2002).

  20. Maria Luisa Bonet, Nicola Galesi. Degree Complexity for a Modified Pigeonhole Principle. Archive for Mathematical Logic. 42(5), pp. 403–414 (2003).

  21. Maria Luisa Bonet, Nicola Galesi. Optimality of Size-Width tradeoffs for Resolution. Computational Complexity. 10(4), pp. 261–276 (2001)

  22. Alabert Atserias, Nicola Galesi, Ricard Gavalda. Monotone Proofs of the Pigeon Hole Principle. Mathematical Logic Quarterly. 47(4), pp. 461–474 (2001).

  23. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen. On the Relative Complexity of the Resolution Refinements and Cutting Planes Proof Systems. SIAM Journal on Computing. 30(5), pp. 1462–1484. (2000).

  24. S. Caporaso, Michele Zito, Nicola Galesi. A Predicative and Decidable Characterization of the Polynomial Classes of Languages. Theoretical Computer Science Vol. 251(1-2), pp. 83–99 (2001).

  25. Maria Luisa Bonet, Nicola Galesi. Linear Lower Bounds and Simulations in Frege Systems with Substitutions.In Selected Papers of 11-th Computer Science Logic. Edited by W. Thomas and M. Nielsen, Lecture Notes in Computer Science. Vol. 1414 pp. 115–128 (1998).

  26. Nicola Galesi. A syntactic characterization of bounded-rank decision trees in terms of decision lists. RAIRO - Theoretical Informatics and Applications. Vol 31 (2) pp.149–158 (1997).

Conferences

  1. Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin. Depth Lower Bounds in Stabbing Planes for Combinatorial Principles. 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022. LIPIcs 219, Schloss Dagstuhl - Leibniz-Zentrum fu ̈r Informatik 2022, pp 1-18.

  2. Nicola Galesi, Leszek A. Kolodziejczyk, Neil Thapen. Polynomial Calculus Space and Resolution width. IEEE Foundations of Computer Science (FOCS)19, pp. 1325-1337

  3. Nicola Galesi, Dmitry Itsykson, Artur Riazonov, Anastasia Sofronova. Lower bounds for Tseitin Tautologies in Bounded Depth Frege for all Graphs. Mathematical Foundation of Computer Science 19, LIPICS 138 pp 1-25, 2019

  4. Stefan Dancthev, Nicola Galesi, Barnaby Martin. Resolution and the binary encoding of combinatorial principles. Conference on Computational Complexity 19. LIPICS 137 pp 1-25, 2019

  5. Nicola Galesi, Fariba Ranjbar, Michele Zito. Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography. ALGOSENSORS 19, LNCS 11931, pp. 79-95, 2019.Nicola Galesi, Fariba Ranjbar:

  6. Nicola Galesi, F. Ranjbar. Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018. pp.212–222.

  7. Nicola Galesi, Navid Talebanfard, Jacobo Tor ́an:. Cops-Robber Games and the Resolution of Tseitin Formulas. Theory and Applications of Satisfiability Testing - SAT 2018, LNCS 2018. pp. 311–326.

  8. Nicola Galesi, Pavel Pudlak, Neil Thapen. The Space complexity of cutting planes proof systems. IEEE Conference on Computational Complexity 2015. pp. 433–44.

  9. Ilario Bonacina, Nicola Galesi, Neil Thapen. Total Space in Resolution. IEEE Foundations of Computer Science, FOCS 2014, pp. 455–472

  10. Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, Nicola Galesi. Proofs of Space: When Space Is of the Essence. Security and Cryptography for Networks - 9th International Conference, SCN 2014 pp. 538–557

  11. Ilario Bonacina Nicola Galesi. Psuedo-Partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. Innovation in Theoretical Computer Science 2013. Berkeley pp. 455–472

  12. Olaf Beyersdorff, Nicola Galesi, Massimo Lauria and Alexander Razborov. Parameterized Bounded-Depth Frege is Not Optimal. ICALP 2011 . LNCS (1) 2011. pp. 630–641

  13. Lorenzo Carlucci, Nicola Galesi and Massimo Lauria. Paris-Harrington tautologies. IEEE 26th Conference on Computational Complexity, 2011. pp. 93–103.

  14. Olaf Beyersdorff, Nicola Galesi and Massimo Lauria. Parameterized Complexity of DPLL Search Procedures. SAT 2011. LNCS 6695, pp. 5–18. 2011.

  15. Nicola Galesi, Neil Thapen. Resolution as Pebbling Games. Proceedings of SAT 2005 . LNCS, pp. 76–90. 2005

  16. Nicola Galesi, Oliver Kullmann. Polynomial SAT Decision, hypergraph transversal and Hermitian Rank. Proceedings of SAT 2004 LNCS, pp. 89–104. 2004

  17. J. Buresh-Oppenheim, Nicola Galesi. A. Magen, S. Hoory, T. Pitassi. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. 41-th IEEE Symposium on Foundations of Computer Science (FOCS 03) pp. 318–327 (2003).

  18. J.L. Esteban, Nicola Galesi, J. Messner. On the Complexity of Resolution with Bounded Conjunctions. Proceedings of the International Colloquium on Automata, Languages and Program- ming (ICALP 02). Lecture Notes in Computer Science 2380, pp. 220–231, 2002

  19. E. Ben-Sasson, Nicola Galesi. Space Complexity for Random Formulae in Resolution. In Proceedings of the IEEE Conference on Computational Complexity 2001 (CCC 01), pp. 42–51.

  20. A. Atserias, Nicola Galesi, P. Pudlak. Monotone Simulations of nonmonotone Propositional Proofs. IEEE Conference on Computational Complexity 2001 (CCC 01), pp. 36–41.

  21. A. Atserias, Nicola Galesi, R. Gavalda. Monotone Proofs of the Pigeon Hole Principle. International Colloquium on Automata and Language Programming, (ICALP 00). Lecture Notes in Computer Science Vol. 1853. pp. 151–162 (2000).

  22. M.L. Bonet, Nicola Galesi. A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. 40-th IEEE Symposium on Foundations of Computer Science (FOCS 99) pp.422–431 (1999). Errata-Corrige: In the conference version of the paper is claimed the side result that the resolution refutations presented for the ordering principle are linear. The claim in the paper is wrong, but it was proved correctly in the paper by S. Buss and J. Johannsen: On linear Resolution . See also the journal version of my paper.

  23. M.L. Bonet, J.L. Esteban, Nicola Galesi, J. Johannsen. Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. 39-th IEEE Symposium on Foundations of Computer Science (FOCS 98) pp. 638–647 (1998).

  24. M.L. Bonet, Nicola Galesi. Linear Lower Bounds and Simulations in Frege Systems with Substitutions. 11-th Computer Science Logic. pp. 109–119 (CSL 97)

  25. S. Caporaso, M. Zito, Nicola Galesi, E. Covino. Syntactic Characterization in LISP of the Polynomial Complexity Classes and Hierarchy. Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC 97). Lecture Notes in Computer Science. 1203, pp. 61–73 (1997)

  26. V. De Florio, Nicola Galesi, F.P. Murgolo, V. Spinelli. Towards an implementation of the Linda Model into the Parallel Virtual Machine. Conference Proceedings of the European Conference of Convex Users Group. Bilbao, Spain, pp. 1–18 (1993).