Jan Johannsen

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