Follow
Nicola Galesi
Nicola Galesi
Verified email at uniroma1.it - Homepage
Title
Cited by
Cited by
Year
Proofs of space: When space is of the essence
G Ateniese, I Bonacina, A Faonio, N Galesi
Security and Cryptography for Networks: 9th International Conference, SCN …, 2014
1602014
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
1172000
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
1112003
Space complexity of random formulae in resolution
E Ben‐Sasson, N Galesi
Random Structures & Algorithms 23 (1), 92-109, 2003
1032003
Optimality of size-width tradeoffs for resolution
ML Bonet, N Galesi
computational complexity 10, 261-276, 2001
982001
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
741999
On the complexity of resolution with bounded conjunctions
JL Esteban, N Galesi, J Messner
Theoretical Computer Science 321 (2-3), 347-370, 2004
512004
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
511998
Optimality of size-degree tradeoffs for polynomial calculus
N Galesi, M Lauria
ACM Transactions on Computational Logic (TOCL) 12 (1), 1-22, 2010
452010
Monotone simulations of non-monotone proofs
A Atserias, N Galesi, P Pudlák
Journal of Computer and System Sciences 65 (4), 626-638, 2002
412002
A characterization of tree-like resolution size
O Beyersdorff, N Galesi, M Lauria
Information Processing Letters 113 (18), 666-671, 2013
362013
Total space in resolution
I Bonacina, N Galesi, N Thapen
SIAM Journal on Computing 45 (5), 1894-1909, 2016
342016
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
332010
Parameterized complexity of DPLL search procedures
O Beyersdorff, N Galesi, M Lauria
ACM Transactions on Computational Logic (TOCL) 14 (3), 1-21, 2013
322013
Polynomial time SAT decision, hypergraph transversals and the hermitian rank
N Galesi, O Kullmann
Theory and Applications of Satisfiability Testing: 7th International …, 2005
262005
A framework for space complexity in algebraic proof systems
I Bonacina, N Galesi
Journal of the ACM (JACM) 62 (3), 1-20, 2015
252015
On the automatizability of polynomial calculus
N Galesi, M Lauria
Theory of Computing Systems 47 (2), 491-506, 2010
242010
The space complexity of cutting planes refutations
N Galesi, P Pudlák, N Thapen
Leibniz International Proceedings in Informatics, LIPIcs 33, 433-447, 2015
232015
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
232012
Monotone proofs of the pigeon hole principle
A Atserias, N Galesi, R Gavaldá
Mathematical Logic Quarterly: Mathematical Logic Quarterly 47 (4), 461-474, 2001
222001
The system can't perform the operation now. Try again later.
Articles 1–20