Nicola Galesi

Orcid: 0000-0002-8522-362X

According to our database1, Nicola Galesi authored at least 51 papers between 1997 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Vertex-connectivity for node failure identification in Boolean Network Tomography.
Inf. Process. Lett., February, 2024

2023
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.
Comput. Complex., December, 2023

On the Algebraic Proof Complexity of Tensor Isomorphism.
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.
Theor. Comput. Sci., 2022

2021
Depth lower bounds in Stabbing Planes for combinatorial principles.
Electron. Colloquium Comput. Complex., 2021

Counting and localizing defective nodes by Boolean network tomography.
CoRR, 2021

2020
Proof complexity and the binary encoding of combinatorial principles.
CoRR, 2020

2019
Polynomial calculus space and resolution width.
Electron. Colloquium Comput. Complex., 2019

Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Electron. Colloquium Comput. Complex., 2019

2018
Cops-Robber games and the resolution of Tseitin formulas.
Electron. Colloquium Comput. Complex., 2018

Resolution and the binary encoding of combinatorial principles.
Electron. Colloquium Comput. Complex., 2018

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

Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography.
Proceedings of the 38th IEEE International Conference on Distributed Computing Systems, 2018

2017
Space proof complexity for random 3-CNFs.
Inf. Comput., 2017

2016
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies.
ACM Trans. Comput. Log., 2016

2015
A Framework for Space Complexity in Algebraic Proof Systems.
J. ACM, 2015

2014
The space complexity of cutting planes refutations.
Electron. Colloquium Comput. Complex., 2014

Total space in resolution.
Electron. Colloquium Comput. Complex., 2014

Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem.
Electron. Colloquium Comput. Complex., 2014

2013
Parameterized Complexity of DPLL Search Procedures.
ACM Trans. Comput. Log., 2013

A characterization of tree-like Resolution size.
Inf. Process. Lett., 2013

Proofs of Space: When Space is of the Essence.
IACR Cryptol. ePrint Arch., 2013

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

SAT Interactions (Dagstuhl Seminar 12471).
Dagstuhl Reports, 2012

2010
Optimality of size-degree tradeoffs for polynomial calculus.
ACM Trans. Comput. Log., 2010

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games.
Inf. Process. Lett., 2010

Paris-Harrington tautologies.
Electron. Colloquium Comput. Complex., 2010

Parameterized Bounded-Depth Frege is Not Optimal.
Electron. Colloquium Comput. Complex., 2010

Hardness of Parameterized Resolution.
Electron. Colloquium Comput. Complex., 2010

2009
On the Automatizability of Polynomial Calculus.
Electron. Colloquium Comput. Complex., 2009

2007
Extending Polynomial Calculus to $k$-DNF Resolution.
Electron. Colloquium Comput. Complex., 2007

2006
Rank Bounds and Integrality Gaps for Cutting Planes Procedures.
Theory Comput., 2006

2004
On the complexity of resolution with bounded conjunctions.
Theor. Comput. Sci., 2004

Resolution and pebbling games
Electron. Colloquium Comput. Complex., 2004

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

The Complexity of Treelike Systems over lamda-Local Formulae.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003
Degree complexity for a modified pigeonhole principle.
Arch. Math. Log., 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Monotone simulations of non-monotone proofs.
J. Comput. Syst. Sci., 2002

2001
A predicative and decidable characterization of the polynomial classes of languages.
Theor. Comput. Sci., 2001

Monotone Proofs of the Pigeon Hole Principle.
Math. Log. Q., 2001

Space Complexity of Random Formulae in Resolution
Electron. Colloquium Comput. Complex., 2001

Optimality of size-width tradeoffs for resolution.
Comput. Complex., 2001

Monotone Simulations of Nonmonotone Proofs.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.
SIAM J. Comput., 2000

Monotone simulations of nonmonotone propositional proofs
Electron. Colloquium Comput. Complex., 2000

1999
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems
Electron. Colloquium Comput. Complex., 1998

1997
A Syntactic Characterization of Bounded-Rank Decision Trees in Terms of Decision Lists.
RAIRO Theor. Informatics Appl., 1997

Linear Lower Bounds and Simulations in Frege Systems with Substitutions.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

Syntactic Characterization in LISP of the Polynominal Complexity Classes and Hierarchy.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997


  Loading...