Nicola Galesi

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.
 Manuscripts Journals
 Conferences Thesis


Manuscripts

[2] Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, and Paul Wollan
Space proof complexity for random 3-CNFs,
Submitted
 Pdf

[2] Nicola Galesi
A note on simulating substitutions with extensions for Frege systems.
 Pdf




Journals

[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)