Nicola Galesi

HomePublications Pubs Teaching Teach Talks News

Publications

The copyrights belongs to the publisher. All papers are preprints essentially equivalent to the published versions, and can be only downloaded for academic purposes.
 Recents Journals
 Conferences Thesis


Recents


Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs  
Mathematical Foundations of Computer Science (MFCS 2019)
  Pdf

Nicola Galesi, Fariba Ranjbar, Michele Zito
Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography  
ALGOSENSORS 2019
  Pdf

Nicola Galesi, Leszek Ko?odziejczyk, Neil Thapen
Polynomial calculus space and resolution width  
IEEE Foundations of Computer Science (FOCS 2019)
  Pdf

Stefan Dantchev, Nicola Galesi, Barnaby Martin,
Resolution and the binary encoding of combinatorial principles  
Conference on Computational Complexity 2019 (CCC 19)
  Pdf

Nicola Galesi, Navid Talebanfard, Jacobo Toràn
Cops-Robber games and the resolution of Tseitin formulas 
The 21st International Conference on Theory and Applications of Satisfiability Testing (SAT 18).
  Pdf


Nicola Galesi, Fariba Ranjbar
Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography. 
IEEE  Conference on Distributed and  Computing Systems (ICDCS 2018).
  Pdf


Journals

[23] Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, and Paul Wollan
Space proof complexity for random 3-CNFs,
Information and Computation 2017
 Pdf
Publisher
[22] Ilario Bonacina, Nicola Galesi, Neil Thapen.
Total Space in Resolution
Siam Journal on Computing. 45(5): 1894-1909 (2016)
 Pdf
Publisher
[21] Lorenzo Carlucci, Nicola Galesi and Massimo Lauria.
Paris-Harrington tautologies.
ACM Transactions on Computational Logic. 17(4) Sept. 2016
 Pdf
Publisher
[20] Ilario Bonacina, Nicola Galesi.
A framework for space complexity in algebraic proof systems.
Journal of the ACM. 62(3): 23 (2015)
 Pdf
Publisher
[19] Olaf Beyersdorff, Nicola Galesi and Massimo Lauria.
A characterization of tree-like Resolution size.
Information Processing Letters 113(18): 666-671 (2013)
 Pdf
Publisher
[18] Olaf Beyersdorff, Nicola Galesi and Massimo Lauria.
Parameterized Complexity of DPLL Search Procedure
ACM Transactions on Computational Logic. 14(3). 2013
 Pdf
Publisher
[17] Olaf Beyersdorff, Nicola Galesi and Massimo Lauria, Alexander Razborov.
Parameterized Bounded-Depth Frege is not Optimal
ACM Transactions on Computation Theory (TOCT). 4(3), pp. 2012.
 Pdf
Publisher
[16] 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):1074-1077 2010
 Pdf
Publisher
[15] Nicola Galesi, M Lauria.
Optimality of size-degree trade-offs for Polynomial Calculus
ACM Transactions on Computational Logic. 12(1). pp. 2010.
 Pdf
Publisher
[14] Nicola Galesi, M. Lauria
On the Automatizability of Polynomial Calculus.
Theory of computing Systems 47(2). pp. 491–506. 2011
 Pdf
Publisher
[13] J.Buresh-Oppenheim, Nicola Galesi, A. Magen, T. Pitassi. S. Hoory.  Rank Bounds and Integrality Gaps for Cutting Planes Procedures . Theory of Computing. 2(1) pp. 65–90, 2006.
 Pdf
Publisher
[12] Nicola Galesi, Nicola Thapen.
Resolution and Pebbling Games
Selected Papers of SAT 05, Lecture Notes in Computer Science 3596, pp. 76–90, 2006. 
 Pdf
Publisher
[11] Nicola Galesi, O. Kullmann.
Polynomial SAT decision, hypergraph transversals and Hermitian rank
Selected Papers of SAT 04, Lecture Notes in Computer Science 3542, pp. 89–104., 2005
 Pdf
Publisher
[10] J.L Esteban, Nicola Galesi, J. Messner.
On the Complexity of Resolution with Bounded Conjunctions. Theoretical Computer Science. 21(2-3)pp. 347-370 2004
 Pdf
Publisher
[9] E. Ben-Sasson, Nicola Galesi
Space Complexity for Random Formulae in Resolution.
Random Structures and Algorithms, 2003. Vol 23(1). 2003 pp.92-109.
 Pdf
Publisher
[8] A. Atserias, Nicola Galesi, P. Pudlàk.
Monotone Simulations of nonmonotone Propositional Proofs.
Journal of Computer and System Science. 65(4): 626-638 (2002)
 Pdf
Publisher
[7] M. L. Bonet, Nicola Galesi.
Degree Lower Bounds for a Modified Pigeonhole Principle. Archive for Mathematical Logic. 42(5): 403-414 (2003)
 Pdf
Publisher
[6] M. L. Bonet, Nicola Galesi.
Optimality of Size-Width tradeoffs for Resolution. Computational Complexity. 10(4): 261-276 (2001)
 Pdf
Publisher
[5] A. Atserias, Nicola Galesi, R. Gavalda.
Monotone Proofs of the Pigeon Hole Principle.
Mathematical Logic Quarterly. 47(4) pp. 461-474 (2001).
 Pdf
Publisher
[4] M. L. Bonet, J.L. Esteban, Nicola Galesi, J.Johannsen.
On the Relative Complexity of the Resolution Refinements and Cutting Planes Proof Systems. SIAM Journal on Computing. 30(5) pp. 1462-1484. (2000).
 Pdf
Publisher
[3] S. Caporaso, M. 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).
 Pdf
Publisher
[2] M.L. Bonet, Nicola Galesi.
Linear Lower Bounds and Simulations in Frege Systems with Substitutions.
In Selected Papers of 11-th Computer Science Logic. LNCS. Vol. 1414 pp. 115-128 (1998).
 Pdf
Publisher
[1] 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).
 Pdf
Publisher

Conference Proceedings

[20] Nicola Galesi, Pavel Pudlak, Neil Thapen.
The Space complexity of cutting planes proof systems
Conference on Computational Complexity 2015. pp. 433-447
Publisher
[19] Ilario Bonacina, Nicola Galesi, Neil Thapen.
Total Space in Resolution
IEEE Foundations of Computer Science, FOCS 2014 pp. 455-472
 Pdf
Publisher
[18] 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
 Pdf
Publisher
[17 ] 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
 Pdf
Publisher
[16] Olaf Beyersdorff, Nicola Galesi, Massimo Lauria and Alexander Razborov.
Parameterized Bounded-Depth Frege is Not Optimal
ICALP 2011 . LNCS (1) 2011. pp. 630-641
 Pdf
Publisher
[15] Lorenzo Carlucci, Nicola Galesi and Massimo Lauria.
Paris-Harrington tautologies
IEEE 26th Conference on Computational Complexity, 2011. pp. 93-103.
 Pdf
Publisher
[14] Olaf Beyersdorff, Nicola Galesi and Massimo Lauria.
Parameterized Complexity of DPLL Search Procedures
SAT 2011. LNCS 6695, pp 5-18. 2011.
 Pdf
Publisher
[13] Nicola Galesi, Neil Thapen
Resolution as Pebbling Games
Proceedings of SAT 2005 . LNCS, pp. 76-90. 2005
 Pdf
Publisher
[12]  Nicola Galesi, Oliver Kullmann
Polynomial SAT Decision, hypergraph transversal and Hermitian Rank.
Proceedings of SAT 2004 LNCS, pp. 89-104. 2004
 Pdf
Publisher
[11] Nicola Galesi, Neil Thapen.
The complexity of treelike Systems over ?-local Formulae.
IEEE Conference on Computational Complexity 2004: 68-74
 Pdf
Publisher
[10] 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).
 Pdf
Publisher
[9] J.L. Esteban, Nicola Galesi, J. Messner.
On the Complexity of Resolution with Bounded Conjunctions.
International Colloquium on Automata, Languages and Programming (ICALP 02). Lecture Notes in Computer Science 2380, pp. 220-231, 2002
 Pdf
Publisher
[8] 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.
 Pdf
Publisher
[7] A. Atserias, Nicola Galesi, P. Pudlak.
Monotone Simulations of nonmonotone Propositional Proofs.
IEEE Conference on Computational Complexity 2001 (CCC 01), pp. 36-41.
 Pdf
Publisher
[6] 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).
 Pdf
Publisher
[5] 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).
 Pdf
Publisher
[4] M.L. Bonet, J.L. Esteban, Nicola Galesi, J. Johannsen 3
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).
 Pdf
Publisher
[3] 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)
 Pdf
Publisher
[2] 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)
 Pdf
Publisher

Thesis

Nicola Galesi
On the complexity of propositional proof systems. Univeristat Poitecnica de Catalunya (2000)
Nicola Galesi
LISP-RP-un sottolinguaggio del LISP.                                         Università degli Studi di Bari (1993)