Nicola Galesi

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 32

Top Topics

Space Complexity

Neighboring Nodes

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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