Nicola Galesi

According to our database, Nicola Galesi authored at least 52 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Vertex-connectivity for node failure identification in Boolean Network Tomography.

Nicola Galesi, Fariba Ranjbar, Michele Zito

Inf. Process. Lett., February, 2024

Proof Complexity and the Binary Encoding of Combinatorial Principles.

Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

SIAM J. Comput., 2024

The Complexity of Boolean Failure Identification.

Nicola Galesi, Fariba Ranjbar

Proceedings of the 25th Italian Conference on Theoretical Computer Science, 2024

2023

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.

Ilario Bonacina, Nicola Galesi, Massimo Lauria

Comput. Complex., December, 2023

On the Algebraic Proof Complexity of Tensor Isomorphism.

Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Tight bounds to localize failure nodes on trees, grids and through embeddings under boolean network tomography.

Nicola Galesi, Fariba Ranjbar

Theor. Comput. Sci., 2022

2021

Depth lower bounds in Stabbing Planes for combinatorial principles.

Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

Electron. Colloquium Comput. Complex., 2021

Counting and localizing defective nodes by Boolean network tomography.

Nicola Galesi, Fariba Ranjbar

CoRR, 2021

2019

Polynomial calculus space and resolution width.

Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen

Electron. Colloquium Comput. Complex., 2019

Bounded-depth Frege complexity of Tseitin formulas for all graphs.

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2019

2018

Cops-Robber games and the resolution of Tseitin formulas.

Nicola Galesi, Navid Talebanfard, Jacobo Torán

Electron. Colloquium Comput. Complex., 2018

Resolution and the binary encoding of combinatorial principles.

Stefan S. Dantchev, Nicola Galesi, Barnaby Martin

Electron. Colloquium Comput. Complex., 2018

Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography.

Nicola Galesi, Fariba Ranjbar, Michele Zito

CoRR, 2018

Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography.

Nicola Galesi, Fariba Ranjbar

Proceedings of the 38th IEEE International Conference on Distributed Computing Systems, 2018

2017

Space proof complexity for random 3-CNFs.

Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan

Inf. Comput., 2017

2016

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies.

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2016

Total Space in Resolution.

Ilario Bonacina, Nicola Galesi, Neil Thapen

SIAM J. Comput., 2016

2015

A Framework for Space Complexity in Algebraic Proof Systems.

Ilario Bonacina, Nicola Galesi

J. ACM, 2015

2014

The space complexity of cutting planes refutations.

Nicola Galesi, Pavel Pudlák, Neil Thapen

Electron. Colloquium Comput. Complex., 2014

Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem.

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

Electron. Colloquium Comput. Complex., 2014

2013

Parameterized Complexity of DPLL Search Procedures.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2013

A characterization of tree-like Resolution size.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Inf. Process. Lett., 2013

Proofs of Space: When Space is of the Essence.

Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, Nicola Galesi

IACR Cryptol. ePrint Arch., 2013

2012

Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems.

Ilario Bonacina, Nicola Galesi

Electron. Colloquium Comput. Complex., 2012

SAT Interactions (Dagstuhl Seminar 12471).

Nadia Creignou, Nicola Galesi, Oliver Kullmann, Heribert Vollmer

Dagstuhl Reports, 2012

2010

Optimality of size-degree tradeoffs for polynomial calculus.

Nicola Galesi, Massimo Lauria

ACM Trans. Comput. Log., 2010

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Inf. Process. Lett., 2010

Paris-Harrington tautologies.

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2010

Parameterized Bounded-Depth Frege is Not Optimal.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2010

Hardness of Parameterized Resolution.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2010

2009

On the Automatizability of Polynomial Calculus.

Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2009

2007

Extending Polynomial Calculus to $k$-DNF Resolution.

Nicola Galesi, Massimo Lauria

Electron. Colloquium Comput. Complex., 2007

2006

Rank Bounds and Integrality Gaps for Cutting Planes Procedures.

Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi

Theory Comput., 2006

2004

On the complexity of resolution with bounded conjunctions.

Juan Luis Esteban, Nicola Galesi, Jochen Messner

Theor. Comput. Sci., 2004

Resolution and pebbling games

Nicola Galesi, Neil Thapen

Electron. Colloquium Comput. Complex., 2004

Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank.

Nicola Galesi, Oliver Kullmann

Proceedings of the Theory and Applications of Satisfiability Testing, 2004

The Complexity of Treelike Systems over lamda-Local Formulae.

Nicola Galesi, Neil Thapen

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Degree complexity for a modified pigeonhole principle.

Maria Luisa Bonet, Nicola Galesi

Arch. Math. Log., 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.

Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Monotone simulations of non-monotone proofs.

Albert Atserias, Nicola Galesi, Pavel Pudlák

J. Comput. Syst. Sci., 2002

2001

A predicative and decidable characterization of the polynomial classes of languages.

Salvatore Caporaso, Michele Zito, Nicola Galesi

Theor. Comput. Sci., 2001

Space Complexity of Random Formulae in Resolution

Eli Ben-Sasson, Nicola Galesi

Electron. Colloquium Comput. Complex., 2001

Optimality of size-width tradeoffs for resolution.

Maria Luisa Bonet, Nicola Galesi

Comput. Complex., 2001

Monotone Simulations of Nonmonotone Proofs.

Albert Atserias, Nicola Galesi, Pavel Pudlák

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen

SIAM J. Comput., 2000

Monotone simulations of nonmonotone propositional proofs

Albert Atserias, Nicola Galesi, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2000

Monotone Proofs of the Pigeon Hole Principle

Albert Atserias, Nicola Galesi, Ricard Gavaldà

Electron. Colloquium Comput. Complex., 2000

1999

A Study of Proof Search Algorithms for Resolution and Polynomial Calculus.

Maria Luisa Bonet, Nicola Galesi

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen

Electron. Colloquium Comput. Complex., 1998

1997

A Syntactic Characterization of Bounded-Rank Decision Trees in Terms of Decision Lists.

Nicola Galesi

RAIRO Theor. Informatics Appl., 1997

Linear Lower Bounds and Simulations in Frege Systems with Substitutions.

Maria Luisa Bonet, Nicola Galesi

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

Syntactic Characterization in LISP of the Polynominal Complexity Classes and Hierarchy.

Salvatore Caporaso, Michele Zito, Nicola Galesi, Emanuele Covino

Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997