Nicola Galesi

94 papers A* 7A 14B 3C 2Misc 1Journal 63Unranked 4
YearRankTypeTitle / Venue / Authors
2025 J jnl
Cluster deletion and clique partitioning in graphs with bounded clique number.
CoRR
Nicola Galesi, Tony Huynh, Fariba Ranjbar
2025 J jnl
Polynomial Calculus Space and Resolution Width.
Theory Comput.
Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen
2025 J jnl
The complexity of boolean failure identification.
Theor. Comput. Sci.
Nicola Galesi, Fariba Ranjbar
2024 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
Log. Methods Comput. Sci.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2024 J jnl
Proof Complexity and the Binary Encoding of Combinatorial Principles.
SIAM J. Comput.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2024 — conf
The Complexity of Boolean Failure Identification.
ICTCS
Nicola Galesi, Fariba Ranjbar
2024 J jnl
Vertex-connectivity for node failure identification in Boolean Network Tomography.
Inf. Process. Lett.
Nicola Galesi, Fariba Ranjbar, Michele Zito
2023 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Ann. Pure Appl. Log.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2023 A conf
On the Algebraic Proof Complexity of Tensor Isomorphism.
CCC
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
2023 J jnl
On the algebraic proof complexity of Tensor Isomorphism.
CoRR
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
2023 J jnl
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.
Comput. Complex.
Ilario Bonacina, Nicola Galesi, Massimo Lauria
2022 A conf
Depth Lower Bounds in Stabbing Planes for Combinatorial Principles.
STACS
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2022 B conf
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares.
MFCS
Ilario Bonacina, Nicola Galesi, Massimo Lauria
2022 J jnl
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.
Electron. Colloquium Comput. Complex.
Ilario Bonacina, Nicola Galesi, Massimo Lauria
2022 J jnl
Tight bounds to localize failure nodes on trees, grids and through embeddings under boolean network tomography.
Theor. Comput. Sci.
Nicola Galesi, Fariba Ranjbar
2021 J jnl
Counting and localizing defective nodes by Boolean network tomography.
CoRR
Nicola Galesi, Fariba Ranjbar
2021 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2021 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
Electron. Colloquium Comput. Complex.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2020 J jnl
Cops-Robber Games and the Resolution of Tseitin Formulas.
ACM Trans. Comput. Theory
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2020 J jnl
Proof complexity and the binary encoding of combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2019 B conf
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs.
MFCS
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2019 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2019 A* conf
Polynomial Calculus Space and Resolution Width.
FOCS
Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen
2019 J jnl
Polynomial calculus space and resolution width.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen
2019 A conf
Resolution and the Binary Encoding of Combinatorial Principles.
CCC
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2019 C conf
Vertex-Connectivity for Node Failure Identification in Boolean Network Tomography.
ALGOSENSORS
Nicola Galesi, Fariba Ranjbar, Michele Zito
2018 A conf
Cops-Robber Games and the Resolution of Tseitin Formulas.
SAT
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2018 J jnl
Cops-Robber games and the resolution of Tseitin formulas.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2018 J jnl
Resolution and the binary encoding of combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2018 J jnl
Resolution and the binary encoding of combinatorial principles.
Electron. Colloquium Comput. Complex.
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2018 A conf
Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography.
ICDCS
Nicola Galesi, Fariba Ranjbar
2018 J jnl
Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography.
CoRR
Nicola Galesi, Fariba Ranjbar, Michele Zito
2017 J jnl
Space proof complexity for random 3-CNFs.
Inf. Comput.
Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan
2017 J jnl
Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography.
CoRR
Nicola Galesi, Fariba Ranjbar
2016 J jnl
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies.
ACM Trans. Comput. Log.
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
2016 J jnl
Total Space in Resolution.
SIAM J. Comput.
Ilario Bonacina, Nicola Galesi, Neil Thapen
2015 J jnl
A Framework for Space Complexity in Algebraic Proof Systems.
J. ACM
Ilario Bonacina, Nicola Galesi
2015 J jnl
Space proof complexity for random 3-CNFs.
CoRR
Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan
2015 A conf
The Space Complexity of Cutting Planes Refutations.
CCC
Nicola Galesi, Pavel Pudlák, Neil Thapen
2014 Misc conf
Proofs of Space: When Space Is of the Essence.
SCN
Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, Nicola Galesi
2014 J jnl
Space proof complexity for random $3$-CNFs via a $(2-ε)$-Hall's Theorem.
CoRR
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan
2014 J jnl
Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem.
Electron. Colloquium Comput. Complex.
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan
2014 J jnl
The space complexity of cutting planes refutations.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Pavel Pudlák, Neil Thapen
2014 A* conf
Total Space in Resolution.
FOCS
Ilario Bonacina, Nicola Galesi, Neil Thapen
2014 J jnl
Total space in resolution.
Electron. Colloquium Comput. Complex.
Ilario Bonacina, Nicola Galesi, Neil Thapen
2013 J jnl
A characterization of tree-like Resolution size.
Inf. Process. Lett.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2013 J jnl
Parameterized Complexity of DPLL Search Procedures.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2013 J jnl
Proofs of Space: When Space is of the Essence.
IACR Cryptol. ePrint Arch.
Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, Nicola Galesi
2013 A conf
Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems.
ITCS
Ilario Bonacina, Nicola Galesi
2012 J jnl
A Characterization of Tree-Like Resolution Size.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2012 J jnl
Parameterized Bounded-Depth Frege Is not Optimal.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2012 J jnl
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems.
Electron. Colloquium Comput. Complex.
Ilario Bonacina, Nicola Galesi
2012 J jnl
SAT Interactions (Dagstuhl Seminar 12471).
Dagstuhl Reports
Nadia Creignou, Nicola Galesi, Oliver Kullmann, Heribert Vollmer
2011 — conf
Parameterized Bounded-Depth Frege Is Not Optimal.
ICALP (1)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2011 A conf
Parameterized Complexity of DPLL Search Procedures.
SAT
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2011 A conf
Paris-Harrington Tautologies.
CCC
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
2010 J jnl
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games.
Inf. Process. Lett.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 — conf
Hardness of Parameterized Resolution.
Circuits, Logic, and Games
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
Hardness of Parameterized Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
On the Automatizability of Polynomial Calculus.
Theory Comput. Syst.
Nicola Galesi, Massimo Lauria
2010 J jnl
Optimality of size-degree tradeoffs for polynomial calculus.
ACM Trans. Comput. Log.
Nicola Galesi, Massimo Lauria
2010 J jnl
Parameterized Bounded-Depth Frege is Not Optimal.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2010 J jnl
Paris-Harrington tautologies.
Electron. Colloquium Comput. Complex.
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria
2009 J jnl
On the Automatizability of Polynomial Calculus.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Massimo Lauria
2007 J jnl
Extending Polynomial Calculus to $k$-DNF Resolution.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Massimo Lauria
2006 J jnl
Rank Bounds and Integrality Gaps for Cutting Planes Procedures.
Theory Comput.
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
2005 A conf
Resolution and Pebbling Games.
SAT
Nicola Galesi, Neil Thapen
2004 J jnl
On the complexity of resolution with bounded conjunctions.
Theor. Comput. Sci.
Juan Luis Esteban, Nicola Galesi, Jochen Messner
2004 A conf
Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank.
SAT
Nicola Galesi, Oliver Kullmann
2004 — conf
Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank.
SAT (Selected Papers
Nicola Galesi, Oliver Kullmann
2004 J jnl
Resolution and pebbling games
Electron. Colloquium Comput. Complex.
Nicola Galesi, Neil Thapen
2004 A conf
The Complexity of Treelike Systems over lamda-Local Formulae.
CCC
Nicola Galesi, Neil Thapen
2003 J jnl
Degree complexity for a modified pigeonhole principle.
Arch. Math. Log.
Maria Luisa Bonet, Nicola Galesi
2003 A* conf
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
FOCS
Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
2003 J jnl
Space complexity of random formulae in resolution.
Random Struct. Algorithms
Eli Ben-Sasson, Nicola Galesi
2002 J jnl
Monotone simulations of non-monotone proofs.
J. Comput. Syst. Sci.
Albert Atserias, Nicola Galesi, Pavel Pudlák
2002 A* conf
On the Complexity of Resolution with Bounded Conjunctions.
ICALP
Juan Luis Esteban, Nicola Galesi, Jochen Messner
2001 J jnl
A predicative and decidable characterization of the polynomial classes of languages.
Theor. Comput. Sci.
Salvatore Caporaso, Michele Zito, Nicola Galesi
2001 J jnl
Monotone Proofs of the Pigeon Hole Principle.
Math. Log. Q.
Albert Atserias, Nicola Galesi, Ricard Gavaldà
2001 A conf
Monotone Simulations of Nonmonotone Proofs.
CCC
Albert Atserias, Nicola Galesi, Pavel Pudlák
2001 J jnl
Optimality of size-width tradeoffs for resolution.
Comput. Complex.
Maria Luisa Bonet, Nicola Galesi
2001 J jnl
Space Complexity of Random Formulae in Resolution
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Nicola Galesi
2001 A conf
Space Complexity of Random Formulae in Resolution.
CCC
Eli Ben-Sasson, Nicola Galesi
2000 J jnl
Monotone Proofs of the Pigeon Hole Principle
Electron. Colloquium Comput. Complex.
Albert Atserias, Nicola Galesi, Ricard Gavaldà
2000 A* conf
Monotone Proofs of the Pigeon Hole Principle.
ICALP
Albert Atserias, Nicola Galesi, Ricard Gavaldà
2000 J jnl
Monotone simulations of nonmonotone propositional proofs
Electron. Colloquium Comput. Complex.
Albert Atserias, Nicola Galesi, Pavel Pudlák
2000 J jnl
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.
SIAM J. Comput.
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
1999 A* conf
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus.
FOCS
Maria Luisa Bonet, Nicola Galesi
1998 J jnl
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems
Electron. Colloquium Comput. Complex.
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
1998 A* conf
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems.
FOCS
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
1997 J jnl
A Syntactic Characterization of Bounded-Rank Decision Trees in Terms of Decision Lists.
RAIRO Theor. Informatics Appl.
Nicola Galesi
1997 B conf
Linear Lower Bounds and Simulations in Frege Systems with Substitutions.
CSL
Maria Luisa Bonet, Nicola Galesi
1997 C conf
Syntactic Characterization in LISP of the Polynominal Complexity Classes and Hierarchy.
CIAC
Salvatore Caporaso, Michele Zito, Nicola Galesi, Emanuele Covino