Jan Johannsen

Affiliations:
  • Ludwig Maximilian University of Munich, Germany


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
Backdoors into Two Occurrences.
J. Satisf. Boolean Model. Comput., 2020

Simplified and Improved Separations Between Regular and General Resolution by Lifting.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

2016
On Linear Resolution.
J. Satisf. Boolean Model. Comput., 2016

Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

2014
Improved Separations of Regular Resolution from Clause Learning Proof Systems.
J. Artif. Intell. Res., 2014

2013
Exponential Separations in a Hierarchy of Clause Learning Proof Systems.
Electron. Colloquium Comput. Complex., 2013

2011
Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width.
Proceedings of the IJCAI 2011, 2011

2010
Lower bounds for width-restricted clause learning on small width formulas.
Electron. Colloquium Comput. Complex., 2010

2009
An Exponential Lower Bound for Width-Restricted Clause Learning.
Proceedings of the Theory and Applications of Satisfiability Testing, 2009

2008
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning.
Log. Methods Comput. Sci., 2008

Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.
Proceedings of the Foundations of Software Science and Computational Structures, 2008

2005
An elementary fragment of second-order lambda calculus.
ACM Trans. Comput. Log., 2005

An unexpected separation result in Linearly Bounded Arithmetic.
Math. Log. Q., 2005

The Complexity of Pure Literal Elimination.
J. Autom. Reason., 2005

Bounded Model Checking for All Regular Properties.
Proceedings of the Third International Workshop on Bounded Model Checking, 2005

2004
Satisfiability Problems Complete for Deterministic Logarithmic Space.
Proceedings of the STACS 2004, 2004

2003
CTL<sup>+</sup> Is Complete for Double Exponential Time.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002
An Optimal Lower Bound for Resolution with 2-Conjunctions.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001
Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits.
RAIRO Theor. Informatics Appl., 2001

An Exponential Separation between Regular and General Resolution
Electron. Colloquium Comput. Complex., 2001

Linear Ramified Higher Type Recursion and Parallel Complexity.
Proceedings of the Proof Theory in Computer Science, International Seminar, 2001

2000
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.
SIAM J. Comput., 2000

Cumulative Higher-Order Logic as a Foundation for Set Theory.
Math. Log. Q., 2000

1999
Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

1998
A Remark on Independence Results for Sharply Bounded Arithmetic.
Math. Log. Q., 1998

A Model Theoretic Property of Sharply Bounded Formulae, with some Applications.
Math. Log. Q., 1998

Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes.
Inf. Process. Lett., 1998

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems
Electron. Colloquium Comput. Complex., 1998

On Proofs about Threshold Circuits and Counting Hierarchies.
Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1996
Schwache Fragmente der Arithmetik und Schwellwertschaltkreise beschränkter Tiefe.
PhD thesis, 1996

Equational calculi and constant depth propositional proofs.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
On Sharply Bounded Length Induction.
Proceedings of the Computer Science Logic, 9th International Workshop, 1995

1994
A note on sharply bounded arithmetic.
Arch. Math. Log., 1994

1993
On the Weakness of Sharply Bounded Polynomial Induction.
Proceedings of the Computational Logic and Proof Theory, Third Kurt Gödel Colloquium, 1993


  Loading...