| 2020 | SAT | Simplified and Improved Separations Between Regular and General Resolution by Lifting. | Marc Vinyals, Jan Elffers, Jan Johannsen, Jakob Nordstrm |
| 2016 | SAT | Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. | Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordstrm, Marc Vinyals |
| 2013 | SAT | Exponential Separations in a Hierarchy of Clause Learning Proof Systems. | Jan Johannsen |
| 2011 | IJCAI | Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width. | Eli Ben-Sasson, Jan Johannsen |
| 2010 | SAT | Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas. | Eli Ben-Sasson, Jan Johannsen |
| 2009 | SAT | An Exponential Lower Bound for Width-Restricted Clause Learning. | Jan Johannsen |
| 2008 | FOSSACS | Optimal Lower Bounds on Regular Expression Size Using Communication Complexity. | Hermann Gruber, Jan Johannsen |
| 2004 | STACS | Satisfiability Problems Complete for Deterministic Logarithmic Space. | Jan Johannsen |
| 2003 | ICALP | CTL | Jan Johannsen, Martin Lange |
| 2002 | MFCS | An Optimal Lower Bound for Resolution with 2-Conjunctions. | Jan Johannsen, N. S. Narayanaswamy |
| 2002 | STOC | An exponential separation between regular and general resolution. | Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart |
| 1999 | LICS | Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K. | Jan Johannsen |
| 1998 | FOCS | Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. | Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen |
| 1998 | LICS | On Proofs about Threshold Circuits and Counting Hierarchies. | Jan Johannsen, Chris Pollett |
| 1995 | CSL | On Sharply Bounded Length Induction. | Jan Johannsen |