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 | 176 | 2014 |
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 | 117 | 2000 |
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 | 110 | 2003 |
Space complexity of random formulae in resolution E Ben‐Sasson, N Galesi Random Structures & Algorithms 23 (1), 92-109, 2003 | 106 | 2003 |
Optimality of size-width tradeoffs for resolution ML Bonet, N Galesi computational complexity 10, 261-276, 2001 | 100 | 2001 |
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 | 74 | 1999 |
On the complexity of resolution with bounded conjunctions JL Esteban, N Galesi, J Messner Theoretical Computer Science 321 (2-3), 347-370, 2004 | 53 | 2004 |
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 | 53 | 1998 |
Optimality of size-degree tradeoffs for polynomial calculus N Galesi, M Lauria ACM Transactions on Computational Logic (TOCL) 12 (1), 1-22, 2010 | 48 | 2010 |
Monotone simulations of non-monotone proofs A Atserias, N Galesi, P Pudlák Journal of Computer and System Sciences 65 (4), 626-638, 2002 | 43 | 2002 |
A characterization of tree-like resolution size O Beyersdorff, N Galesi, M Lauria Information Processing Letters 113 (18), 666-671, 2013 | 37 | 2013 |
Total space in resolution I Bonacina, N Galesi, N Thapen SIAM Journal on Computing 45 (5), 1894-1909, 2016 | 35 | 2016 |
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 | 35 | 2010 |
Parameterized complexity of DPLL search procedures O Beyersdorff, N Galesi, M Lauria ACM Transactions on Computational Logic (TOCL) 14 (3), 1-21, 2013 | 33 | 2013 |
A framework for space complexity in algebraic proof systems I Bonacina, N Galesi Journal of the ACM (JACM) 62 (3), 1-20, 2015 | 26 | 2015 |
Polynomial time SAT decision, hypergraph transversals and the hermitian rank N Galesi, O Kullmann Theory and Applications of Satisfiability Testing: 7th International …, 2005 | 26 | 2005 |
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 | 25 | 2012 |
On the automatizability of polynomial calculus N Galesi, M Lauria Theory of Computing Systems 47 (2), 491-506, 2010 | 24 | 2010 |
The space complexity of cutting planes refutations N Galesi, P Pudlák, N Thapen Leibniz International Proceedings in Informatics, LIPIcs 33, 433-447, 2015 | 23 | 2015 |
Monotone proofs of the pigeon hole principle A Atserias, N Galesi, R Gavaldá Mathematical Logic Quarterly: Mathematical Logic Quarterly 47 (4), 461-474, 2001 | 22 | 2001 |