Publications

     More Recent and anuscripts

    Journal

    Conferences

Conference Committes

Journal Editorial Board

Invited Lectures

Software

 

Publications

More recent and Manuscripts

 

     O. Beyersdorff, N. Galesi, M. Lauria.

            The Strength of Parameterized tree-like Resolution

 Manuscript, Submitted

 

 

           N. Galesi, M. Lauria.

Extending Polynomial Calculus with k-DNF Resolution

Electronic Colloquium con Computational Complexity 2007

 

Journal papers

          

           N. Galesi, M. Lauria.

           On the Automatizability of Polynomial Calculus

Theory of Computing Systems. To appear

           

           N. Galesi, M. Lauria.

           Degree Lower bounds for a Graph Ordering Principle

ACM Transactions on Computational Logic. To appear

 

            J. Buresh-Oppenheim, N. Galesi, A. Magen, S. Hoory, T. Pitassi.

Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Theory of Computing 2(1) pp. 65--90, 2006. 

   

          N. Galesi, O. Kullmann.

Polynomial SAT decision, hypergraph transversals and Hermitian rank

SAT 05, LNCS 3542, pp. 89--104.

  

           J.L. Esteban, N. Galesi, J. Messner.

On the Complexity of Resolution with Bounded Conjunctions
Theoretical Computer Science. 321(2-3)pp. 347-370 2004
 

           E. Ben-Sasson, N. Galesi.

Space Complexity of Random Formulae in Resolution.
Random Structures and Algorithms, Vol 23(1). 2003 pp.92-109.
 

  • A. Atserias, N Galesi, P.Pudl_k.

Monotone Simulations of Nonmonotone Proofs.
Journal of Computer and System Sciences, Vol 65. 2002. pp. 626-638.
 

  • M.L. Bonet, N. Galesi.

Degree Complexity for a Modified PigeonHole Principle.
Archive for Mathematical Logic, vol 42 (5). 2003 pp.403-414.
 

  • M.L. Bonet, N. Galesi.

Optimality of Size-Width Tradeoffs for Resolution.
Computational Complexity, Vol 10(4) 2001. pp. 261-276.
 

  • A. Atserias, N Galesi, R. Gavald_.

Monotone Proofs of the Pigeonhole Principle.
Mathematical Logic Quarterly,  Vol. 47(4). 2001,  pp. 461-474.
 

  • M.L. Bonet, J.L. Esteban, N Galesi, J. Johannsen.

On the Relative Complexity of  Resolution Refinements and Cutting Planes Proof Systems.
Siam Journal on Computing, Vol. 30(5). 2000, pp. 1462-1484.
 

  • M.L. Bonet, N. Galesi.

Linear Lower Bounds and Simulations in Frege Systems with Substitutions.
Selected Papers of 11-th CSL, Lecture Notes in Computer Science, Vol 1414. 1998, pp. 115-128.
 

  •  N. Galesi.

A Syntactic Characterization of Bounded-Rank Decision Trees in terms of Decision Lists.
RAIRO-Theoretical Informatics and Applications, Vol 31(2). 1997, pp. 149-158.
 

  •  S. Caporaso, M. Zito, N. Galesi.

A Predicative and Decidable Charcaterization of the Polynomial Classes of Languages.
Theoretical Computer Science, Vol 251(1-2). 2001, pp. 83-99.

 

 

 

Conference Proceedings

  • N. Galesi, N. Thapen.

Resolution and Pebbling Games

SAT 05, LNCS 3569, pp. 76--90

 

  • N. Galesi, N. Thapen.

The Complexity of Treelike Systems over l-Local Formulae
19th IEEE Conference on Computational Complexity (CCC),
Amherst (MA), 2004.

  • J. Buresh-Oppenheim, N. Galesi, A. Magen, S. Hoory, T. Pitassi.

Rank Bounds and Integrality Gaps for Cutting Planes Procedures
44th IEEE Symposium on Foundations of Computer Science (FOCS)
Boston (MA), Usa. October 11-14, 2003. 
 

  • J.L. Esteban, N. Galesi, J. Messner.

On the Complexity of Resolution with Bounded Conjunctions.
29th International Colloquium on Automata, Languages and Programming (ICALP),
Malaga, Spain. July 8-13, 2002.  Lectures Notes in Computer Science 2380, pp. 220-231.
 

  • E. Ben-Sasson, N. Galesi.

Space Complexity of Random Formulae in Resolution.
16th IEEE Conference on Computational Complexity (CCC),
Chicago, Illinois. June 18-21, 2001. pp. 42-51.
 

  • A. Atserias, N. Galesi, P.Pudl_k.

Monotone Simulations of Nonmontone Proofs.
16th IEEE Conference on Computational Complexity (CCC),
Chicago, Illinois, June 18-21, 2001. pp. 36-41.
 

  • A. Atserias, N. Galesi, R. Gavald_.

Monotone Proofs of the Pigeonhole Principle.
27th International Colloquium on Automata, Languages and Programming (ICALP),
Geneva, Switzerland. July 9-15, 2000. pp. 36-41.
 

  • M.L. Bonet, N. Galesi.

A Study of Proof Search Algorithms for Resolution and Polynomial Calculus.
40th IEEE Symposium on Foundations of Computer Science (FOCS),
New York City, New York. October 17-19, 1999. pp. 422-431.
 

  • M.L. Bonet, J.L Esteban, N. Galesi, J. Johannsen.

Exponential Seprations between Restricted Resolution and Cutting Planes Proof Systems.
39th IEEE Symposium on Foundations of Computer Science (FOCS),
Palo Alto, California. November 8-11, 1998. pp. 638-647.
 

  • M.L. Bonet, N. Galesi.

A Linear Lower Bounds and Simulations in Frege Systems with Substitutions.
11th Annual Conference of EACSL, Computer Science Logic (CSL),
Aarhus, Denmark. August 23-29, 1997. pp. .
 

  • S. Caporaso. M. Covino, N. Galesi, M. Zito.

A Syntactic Characterization in LISP of the Polynomial Complexity Classes and Hierarchy.
3rd Italian Conference on Algorithms and Complexity (CIAC),
Rome, Italy. March 12-14, 1997. Lecture Notes in Computer Science 1203. pp. 61-73.

PhD Thesis

Nicola Galesi
On the Complexity of Propositional Proof Systems.
Universitat Polit_cnica de Catalunya, 2000

            Conferences Commitees

                 * Italian Conference on Algorithms and Complexity (CIAC 06) 

                 * Computability in Europe (CiE 2010)

 

           

                Journals Editorial Board

                 Journal on Satisfiability,Boolean Modelling and Computation (JSAT)

 

              Invited Lectures

                 

                    7 mar 2006 Conferenza di Facolt_ di Scienze -- Universit_ La Sapienza

                   Quanto _ complessa una dimostrazione ? [Lucidi]

                 

            Software

                 N. Galesi, A Sabellico,

                 A game-oriented resolution theorem prover [Paper, Software]