Jan Johannsen

Publication Activity (10 Years)

Years Active: 1993-2020
Publications (10 Years): 4

Top Venues

SAT

J. Satisf. Boolean Model. Comput.

CoRR

Electron. Colloquium Comput. Complex.

University of Erlangen-Nuremberg, Germany (PHD)

Education History

University of Erlangen-Nuremberg, Germany

PHD

Publications

Marc Vinyals, Jan Elffers, Jan Johannsen, Jakob Nordström
Simplified and Improved Separations Between Regular and General Resolution by Lifting. SAT (2020)
Jan Johannsen
Backdoors into Two Occurrences. J. Satisf. Boolean Model. Comput. 12 (1) (2020)
Sam Buss, Jan Johannsen
On Linear Resolution. J. Satisf. Boolean Model. Comput. 10 (1) (2016)
Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals
Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. SAT (2016)
Maria Luisa Bonet, Sam Buss, Jan Johannsen
Improved Separations of Regular Resolution from Clause Learning Proof Systems. J. Artif. Intell. Res. 49 (2014)
Jan Johannsen
Exponential Separations in a Hierarchy of Clause Learning Proof Systems. SAT (2013)
Jan Johannsen
Exponential Separations in a Hierarchy of Clause Learning Proof Systems. Electron. Colloquium Comput. Complex. 20 (2013)
Maria Luisa Bonet, Sam Buss, Jan Johannsen
Improved Separations of Regular Resolution from Clause Learning Proof Systems CoRR (2012)
Eli Ben-Sasson, Jan Johannsen
Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width. IJCAI (2011)
Eli Ben-Sasson, Jan Johannsen
Lower bounds for width-restricted clause learning on small width formulas. Electron. Colloquium Comput. Complex. 17 (2010)
Eli Ben-Sasson, Jan Johannsen
Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas. SAT (2010)
Jan Johannsen
An Exponential Lower Bound for Width-Restricted Clause Learning. SAT (2009)
Samuel R. Buss, Jan Hoffmann, Jan Johannsen
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning CoRR (2008)
Samuel R. Buss, Jan Hoffmann, Jan Johannsen
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning. Log. Methods Comput. Sci. 4 (4) (2008)
Hermann Gruber, Jan Johannsen
Optimal Lower Bounds on Regular Expression Size Using Communication Complexity. FoSSaCS (2008)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An Exponential Separation between Regular and General Resolution. Theory Comput. 3 (1) (2007)
Markus Jehle, Jan Johannsen, Martin Lange, Nicolas Rachinsky
Bounded Model Checking for All Regular Properties. Electron. Notes Theor. Comput. Sci. 144 (1) (2006)
Klaus Aehlig, Jan Johannsen
An elementary fragment of second-order lambda calculus. ACM Trans. Comput. Log. 6 (2) (2005)
Jan Johannsen
The Complexity of Pure Literal Elimination. J. Autom. Reason. 35 (1-3) (2005)
Arnold Beckmann, Jan Johannsen
An unexpected separation result in Linearly Bounded Arithmetic. Math. Log. Q. 51 (2) (2005)
Jan Johannsen
Satisfiability Problems Complete for Deterministic Logarithmic Space. STACS (2004)
Jan Johannsen, Martin Lange
Is Complete for Double Exponential Time. ICALP (2003)
Klaus Aehlig, Jan Johannsen
An Elementary Fragment of Second-Order Lambda Calculus CoRR (2002)
Jan Johannsen, N. S. Narayanaswamy
An Optimal Lower Bound for Resolution with 2-Conjunctions. MFCS (2002)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An exponential separation between regular and general resolution. STOC (2002)
Jan Johannsen
Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits. RAIRO Theor. Informatics Appl. 35 (3) (2001)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An Exponential Separation between Regular and General Resolution Electron. Colloquium Comput. Complex. 8 (056) (2001)
Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg, Sebastiaan Terwijn
Linear Ramified Higher Type Recursion and Parallel Complexity. Proof Theory in Computer Science (2001)
Wolfgang Degen, Jan Johannsen
Cumulative Higher-Order Logic as a Foundation for Set Theory. Math. Log. Q. 46 (2) (2000)
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems. SIAM J. Comput. 30 (5) (2000)
Jan Johannsen
Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K. LICS (1999)
Jan Johannsen, Chris Pollett
On Proofs about Threshold Circuits and Counting Hierarchies. LICS (1998)
Jan Johannsen
A Model Theoretic Property of Sharply Bounded Formulae, with some Applications. Math. Log. Q. 44 (1998)
Jan Johannsen
A Remark on Independence Results for Sharply Bounded Arithmetic. Math. Log. Q. 44 (1998)
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. FOCS (1998)
Jan Johannsen
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes. Inf. Process. Lett. 67 (1) (1998)
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems Electron. Colloquium Comput. Complex. 5 (35) (1998)
Jan Johannsen
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes Electron. Colloquium Comput. Complex. 4 (32) (1997)
Jan Johannsen
Equational calculi and constant depth propositional proofs. Proof Complexity and Feasible Arithmetics (1996)
Jan Johannsen
On Sharply Bounded Length Induction. CSL (1995)
Jan Johannsen
A note on sharply bounded arithmetic. Arch. Math. Log. 33 (2) (1994)
Jan Johannsen
On the Weakness of Sharply Bounded Polynomial Induction. Kurt Gödel Colloquium (1993)

Jan Johannsen.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jan Johannsen