Jan Johannsen
Jan Johannsen
Institut für Informatik, LMU München
Verified email at ifi.lmu.de - Homepage
TitleCited byYear
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
962000
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
582002
An exponential separation between regular and general resolution
M Alekhnovich, J Johannsen, T Pitassi, A Urquhart
Theory of Computing 3 (1), 81-102, 2007
512007
Optimal lower bounds on regular expression size using communication complexity
H Gruber, J Johannsen
Foundations of Software Science and Computational Structures, 273-286, 2008
462008
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
461998
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
452008
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
271998
A bounded arithmetic theory for constant depth threshold circuits
J Johannsen
GÖDEL '96, 224-234, 1996
211996
On the -Bit-Comprehension Rule
J Johannsen, C Pollett
Logic Colloquium 98: Proceedings of the Annual European Summer Meeting of …, 1998
20*1998
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
A model‐theoretic property of sharply bounded formulae, with some applications
J Johannsen
Mathematical Logic Quarterly 44 (2), 205-215, 1998
161998
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
152014
Satisfiability problems complete for deterministic logarithmic space
J Johannsen
Annual Symposium on Theoretical Aspects of Computer Science, 317-325, 2004
152004
On the weakness of sharply bounded polynomial induction
J Johannsen
Kurt Gödel Colloquium on Computational Logic and Proof Theory, 223-230, 1993
151993
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
122010
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
111998
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
92016
An elementary fragment of second-order lambda calculus
K Aehlig, J Johannsen
ACM Transactions on Computational Logic 6 (2), 468-480, 2005
92005
Depth lower bounds for monotone semi-unbounded fan-in circuits
J Johannsen
RAIRO-Theoretical Informatics and Applications 35 (3), 277-286, 2001
92001
The system can't perform the operation now. Try again later.
Articles 1–20