Jan Johannsen

According to our database, Jan Johannsen authored at least 34 papers between 1993 and 2020.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2020

Backdoors into Two Occurrences.

Jan Johannsen

J. Satisf. Boolean Model. Comput., 2020

Simplified and Improved Separations Between Regular and General Resolution by Lifting.

Marc Vinyals, Jan Elffers, Jan Johannsen, Jakob Nordström

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

2016

On Linear Resolution.

Sam Buss, Jan Johannsen

J. Satisf. Boolean Model. Comput., 2016

Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.

Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

2014

Improved Separations of Regular Resolution from Clause Learning Proof Systems.

Maria Luisa Bonet, Sam Buss, Jan Johannsen

J. Artif. Intell. Res., 2014

2013

Exponential Separations in a Hierarchy of Clause Learning Proof Systems.

Jan Johannsen

Electron. Colloquium Comput. Complex., 2013

2011

Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width.

Eli Ben-Sasson, Jan Johannsen

Proceedings of the IJCAI 2011, 2011

2010

Lower bounds for width-restricted clause learning on small width formulas.

Eli Ben-Sasson, Jan Johannsen

Electron. Colloquium Comput. Complex., 2010

2009

An Exponential Lower Bound for Width-Restricted Clause Learning.

Jan Johannsen

Proceedings of the Theory and Applications of Satisfiability Testing, 2009

2008

Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning.

Samuel R. Buss, Jan Hoffmann, Jan Johannsen

Log. Methods Comput. Sci., 2008

Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.

Hermann Gruber, Jan Johannsen

Proceedings of the Foundations of Software Science and Computational Structures, 2008

2007

An Exponential Separation between Regular and General Resolution.

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart

Theory Comput., 2007

2005

An elementary fragment of second-order lambda calculus.

Klaus Aehlig, Jan Johannsen

ACM Trans. Comput. Log., 2005

An unexpected separation result in Linearly Bounded Arithmetic.

Arnold Beckmann, Jan Johannsen

Math. Log. Q., 2005

The Complexity of Pure Literal Elimination.

Jan Johannsen

J. Autom. Reason., 2005

Bounded Model Checking for All Regular Properties.

Markus Jehle, Jan Johannsen, Martin Lange, Nicolas Rachinsky

Proceedings of the Third International Workshop on Bounded Model Checking, 2005

2004

Satisfiability Problems Complete for Deterministic Logarithmic Space.

Jan Johannsen

Proceedings of the STACS 2004, 2004

2003

CTL⁺ Is Complete for Double Exponential Time.

Jan Johannsen, Martin Lange

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

An Optimal Lower Bound for Resolution with 2-Conjunctions.

Jan Johannsen, N. S. Narayanaswamy

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001

Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits.

Jan Johannsen

RAIRO Theor. Informatics Appl., 2001

Linear Ramified Higher Type Recursion and Parallel Complexity.

Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg, Sebastiaan Terwijn

Proceedings of the Proof Theory in Computer Science, International Seminar, 2001

2000

On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen

SIAM J. Comput., 2000

Cumulative Higher-Order Logic as a Foundation for Set Theory.

Wolfgang Degen, Jan Johannsen

Math. Log. Q., 2000

1999

Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K.

Jan Johannsen

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

1998

A Remark on Independence Results for Sharply Bounded Arithmetic.

Jan Johannsen

Math. Log. Q., 1998

A Model Theoretic Property of Sharply Bounded Formulae, with some Applications.

Jan Johannsen

Math. Log. Q., 1998

Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes.

Jan Johannsen

Inf. Process. Lett., 1998

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen

Electron. Colloquium Comput. Complex., 1998

On Proofs about Threshold Circuits and Counting Hierarchies.

Jan Johannsen, Chris Pollett

Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1996

Schwache Fragmente der Arithmetik und Schwellwertschaltkreise beschränkter Tiefe.

Jan Johannsen

PhD thesis, 1996

Equational calculi and constant depth propositional proofs.

Jan Johannsen

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995

On Sharply Bounded Length Induction.

Jan Johannsen

Proceedings of the Computer Science Logic, 9th International Workshop, 1995

1994

A note on sharply bounded arithmetic.

Jan Johannsen

Arch. Math. Log., 1994

1993

On the Weakness of Sharply Bounded Polynomial Induction.

Jan Johannsen

Proceedings of the Computational Logic and Proof Theory, Third Kurt Gödel Colloquium, 1993