Follow
Jan Johannsen
Jan Johannsen
Institut für Informatik, LMU München
Verified email at ifi.lmu.de - 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
1162000
An exponential separation between regular and general resolution
M Alekhnovich, J Johannsen, T Pitassi, A Urquhart
Theory of Computing 3 (1), 81-102, 2007
682007
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
652002
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
632008
Optimal lower bounds on regular expression size using communication complexity
H Gruber, J Johannsen
Foundations of Software Science and Computational Structures, 273-286, 2008
532008
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
531998
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
291998
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
241996
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
232014
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
202010
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
182006
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
182000
On the weakness of sharply bounded polynomial induction
J Johannsen
Computational Logic and Proof Theory: Third Kurt Gödel Colloquium, KGC'93 …, 1993
171993
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
152016
Satisfiability problems complete for deterministic logarithmic space
J Johannsen
STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science …, 2004
152004
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
151998
The complexity of pure literal elimination
J Johannsen
Journal of Automated Reasoning 35 (1), 89-95, 2005
142005
A model‐theoretic property of sharply bounded formulae, with some applications
J Johannsen
Mathematical Logic Quarterly 44 (2), 205-215, 1998
141998
The system can't perform the operation now. Try again later.
Articles 1–20