2 citations · 4 across the 7 of their papers we have counts for
9 papers
Cluster deletion in cographs, permutation graphs, and graphs with bounded clique number
Nicola Galesi, Tony Huynh, Fariba Ranjbar +1
The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition problem asks…
On the algebraic proof complexity of Tensor Isomorphism
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi +1
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essen…
Depth lower bounds in Stabbing Planes for combinatorial principles
Stefan Dantchev, Nicola Galesi, Abdul Ghani +1
Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequal…
Counting and localizing defective nodes by Boolean network tomography
Nicola Galesi, Fariba Ranjbar
Identifying defective items in larger sets is a main problem with many applications in real life situations. We consider the problem of localizing defective nodes in networks throu…
Proof complexity and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Abdul Ghani +1
We consider Proof Complexity in light of the unusual binary encoding of certain combinatorial principles. We contrast this Proof Complexity with the normal unary encoding in severa…
Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography
Nicola Galesi, Fariba Ranjbar, Michele Zito
In this paper we study the node failure identification problem in undirected graphs by means of Boolean Network Tomography. We argue that vertex connectivity plays a central role.…
Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in -- an extension of Resolution working on -DNFs instead of clauses -- for families of contradictions given in the {\em un…
Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography
Nicola Galesi, Fariba Ranjbar
We study maximal identifiability, a measure recently introduced in Boolean Network Tomography to characterize networks' capability to localize failure nodes in end-to-end path meas…
Space proof complexity for random 3-CNFs
Patrick Bennett, Ilario Bonacina, Nicola Galesi +3
We investigate the space complexity of refuting -CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random -CNF…