Nicola Galesi
Nicola Galesi
Verified email at di.uniroma1.it - Homepage
Title
Cited by
Cited by
Year
On the relative complexity of resolution refinements and cutting planes proof systems
ML Bonet, JL Esteban, N Galesi, J Johannsen
SIAM Journal on Computing 30 (5), 1462-1484, 2000
992000
Rank bounds and integrality gaps for cutting planes procedures
J Buresh-Oppenheim, N Galesi, S Hoory, A Magen, T Pitassi
44th Annual IEEE Symposium on Foundations of Computer Science, 2003 …, 2003
982003
Proofs of space: When space is of the essence
G Ateniese, I Bonacina, A Faonio, N Galesi
International Conference on Security and Cryptography for Networks, 538-557, 2014
902014
Space complexity of random formulae in resolution
E Ben‐Sasson, N Galesi
Random Structures & Algorithms 23 (1), 92-109, 2003
902003
Optimality of size-width tradeoffs for resolution
ML Bonet, N Galesi
Computational Complexity 10 (4), 261-276, 2001
872001
A study of proof search algorithms for resolution and polynomial calculus
ML Bonet, N Galesi
40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039 …, 1999
721999
Exponential separations between restricted resolution and cutting planes proof systems
ML Bonet, JL Esteban, N Galesi, J Johannsen
Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat …, 1998
471998
On the complexity of resolution with bounded conjunctions
JL Esteban, N Galesi, J Messner
Theoretical Computer Science 321 (2-3), 347-370, 2004
412004
Monotone simulations of non-monotone proofs
A Atserias, N Galesi, P Pudlák
Journal of Computer and System Sciences 65 (4), 626-638, 2002
392002
Optimality of size-degree tradeoffs for polynomial calculus
N Galesi, M Lauria
ACM Transactions on Computational Logic (TOCL) 12 (1), 1-22, 2010
362010
Total space in resolution
I Bonacina, N Galesi, N Thapen
SIAM Journal on Computing 45 (5), 1894-1909, 2016
302016
A characterization of tree-like resolution size
O Beyersdorff, N Galesi, M Lauria
Information Processing Letters 113 (18), 666-671, 2013
292013
Polynomial time SAT decision, hypergraph transversals and the hermitian rank
N Galesi, O Kullmann
International Conference on Theory and Applications of Satisfiability …, 2004
282004
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover–Delayer games
O Beyersdorff, N Galesi, M Lauria
Information Processing Letters 110 (23), 1074-1077, 2010
242010
Parameterized complexity of DPLL search procedures
O Beyersdorff, N Galesi, M Lauria
ACM Transactions on Computational Logic (TOCL) 14 (3), 1-21, 2013
232013
A framework for space complexity in algebraic proof systems
I Bonacina, N Galesi
Journal of the ACM (JACM) 62 (3), 1-20, 2015
202015
On the automatizability of polynomial calculus
N Galesi, M Lauria
Theory of Computing Systems 47 (2), 491-506, 2010
192010
On the complexity of resolution with bounded conjunctions
JL Esteban, N Galesi, J Messner
International Colloquium on Automata, Languages, and Programming, 220-231, 2002
182002
The space complexity of cutting planes refutations
N Galesi, P Pudlák, N Thapen
30th Conference on Computational Complexity (CCC 2015), 2015
172015
Parameterized bounded-depth Frege is not optimal
O Beyersdorff, N Galesi, M Lauria, AA Razborov
ACM Transactions on Computation Theory (TOCT) 4 (3), 1-16, 2012
162012
The system can't perform the operation now. Try again later.
Articles 1–20