| 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 |
| An exponential separation between regular and general resolution M Alekhnovich, J Johannsen, T Pitassi, A Urquhart Theory of Computing 3 (1), 81-102, 2007 | 68 | 2007 |
| An exponential separation between regular and general resolution M Alekhnovich, J Johannsen, T Pitassi, A Urquhart Proceedings 34th ACM Symposium on Theory of Computing (STOC), 448-456, 2002 | 65 | 2002 |
| Resolution trees with lemmas: Resolution refinements that characterize DLL algorithms with clause learning SR Buss, J Hoffmann, J Johannsen Logical Methods in Computer Science 4, 2008 | 63 | 2008 |
| Optimal lower bounds on regular expression size using communication complexity H Gruber, J Johannsen Foundations of Software Science and Computational Structures, 273-286, 2008 | 53 | 2008 |
| 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 |
| is complete for double exponential time J Johannsen, M Lange International Colloquium on Automata, Languages and Programming (ICALP 2003 …, 2003 | 29* | 2003 |
| On proofs about threshold circuits and counting hierarchies J Johannsen, C Pollett Proceedings. Thirteenth Annual IEEE Symposium on Logic in Computer Science …, 1998 | 29 | 1998 |
| On the -Bit-Comprehension Rule J Johannsen, C Pollett Logic Colloquium 98: Proceedings of the Annual European Summer Meeting of …, 1998 | 26* | 1998 |
| A bounded arithmetic theory for constant depth threshold circuits J Johannsen GÖDEL '96, 224-234, 1996 | 25 | 1996 |
| Improved Separations of Regular Resolution from Clause Learning Proof Systems ML Bonet, S Buss, J Johannsen Journal of Artificial Intelligence Research 49, 669-703, 2014 | 23 | 2014 |
| Lower bounds for width-restricted clause learning on small width formulas E Ben-Sasson, J Johannsen International Conference on Theory and Applications of Satisfiability …, 2010 | 20 | 2010 |
| Bounded model checking for all regular properties M Jehle, J Johannsen, M Lange, N Rachinsky Electronic Notes in Theoretical Computer Science 144 (1), 3-18, 2006 | 18 | 2006 |
| Cumulative Higher‐Order Logic as a Foundation for Set Theory W Degen, J Johannsen Mathematical Logic Quarterly: Mathematical Logic Quarterly 46 (2), 147-170, 2000 | 18 | 2000 |
| On the weakness of sharply bounded polynomial induction J Johannsen Computational Logic and Proof Theory: Third Kurt Gödel Colloquium, KGC'93 …, 1993 | 17 | 1993 |
| Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers J Elffers, J Johannsen, M Lauria, T Magnard, J Nordström, M Vinyals Theory and Applications of Satisfiability Testing – SAT 2016, 2016 | 15 | 2016 |
| The complexity of pure literal elimination J Johannsen Journal of Automated Reasoning 35 (1), 89-95, 2005 | 15 | 2005 |
| Satisfiability problems complete for deterministic logarithmic space J Johannsen STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science …, 2004 | 15 | 2004 |
| Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes J Johannsen Information Processing Letters 67 (1), 37-41, 1998 | 15 | 1998 |
| A model‐theoretic property of sharply bounded formulae, with some applications J Johannsen Mathematical Logic Quarterly 44 (2), 205-215, 1998 | 14 | 1998 |
Nicola GalesiSapienza University RomeVerified email at uniroma1.it
