 | 2009 |
|---|
| 29 |       | Jan Johannsen:
An Exponential Lower Bound for Width-Restricted Clause Learning.
SAT 2009: 128-140 |
| 2008 |
|---|
| 28 | | Hermann Gruber,
Jan Johannsen:
Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.
FoSSaCS 2008: 273-286 |
| 27 | | Samuel R. Buss,
Jan Hoffmann,
Jan Johannsen:
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
CoRR abs/0811.1075: (2008) |
| 26 | | Samuel R. Buss,
Jan Hoffmann,
Jan Johannsen:
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning.
Logical Methods in Computer Science 4(4): (2008) |
| 2007 |
|---|
| 25 | | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution.
Theory of Computing 3(1): 81-102 (2007) |
| 2006 |
|---|
| 24 | | Markus Jehle,
Jan Johannsen,
Martin Lange,
Nicolas Rachinsky:
Bounded Model Checking for All Regular Properties.
Electr. Notes Theor. Comput. Sci. 144(1): 3-18 (2006) |
| 2005 |
|---|
| 23 | | Klaus Aehlig,
Jan Johannsen:
An elementary fragment of second-order lambda calculus.
ACM Trans. Comput. Log. 6(2): 468-480 (2005) |
| 22 | | Jan Johannsen:
The Complexity of Pure Literal Elimination.
J. Autom. Reasoning 35(1-3): 89-95 (2005) |
| 21 | | Arnold Beckmann,
Jan Johannsen:
An unexpected separation result in Linearly Bounded Arithmetic.
Math. Log. Q. 51(2): 191-200 (2005) |
| 2004 |
|---|
| 20 | | Jan Johannsen:
Satisfiability Problems Complete for Deterministic Logarithmic Space.
STACS 2004: 317-325 |
| 2003 |
|---|
| 19 | | Jan Johannsen,
Martin Lange:
CTL+ Is Complete for Double Exponential Time.
ICALP 2003: 767-775 |
| 2002 |
|---|
| 18 | | Jan Johannsen,
N. S. Narayanaswamy:
An Optimal Lower Bound for Resolution with 2-Conjunctions.
MFCS 2002: 387-398 |
| 17 | | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An exponential separation between regular and general resolution.
STOC 2002: 448-456 |
| 16 | | Klaus Aehlig,
Jan Johannsen:
An Elementary Fragment of Second-Order Lambda Calculus
CoRR cs.LO/0210022: (2002) |
| 2001 |
|---|
| 15 | | Klaus Aehlig,
Jan Johannsen,
Helmut Schwichtenberg,
Sebastiaan Terwijn:
Linear Ramified Higher Type Recursion and Parallel Complexity.
Proof Theory in Computer Science 2001: 1-21 |
| 14 | | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution
Electronic Colloquium on Computational Complexity (ECCC) 8(056): (2001) |
| 13 | | Jan Johannsen:
Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits.
ITA 35(3): 277-286 (2001) |
| 2000 |
|---|
| 12 | | Wolfgang Degen,
Jan Johannsen:
Cumulative Higher-Order Logic as a Foundation for Set Theory.
Math. Log. Q. 46(2): 147-170 (2000) |
| 11 | | 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): 1462-1484 (2000) |
| 1999 |
|---|
| 10 | | Jan Johannsen:
Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K.
LICS 1999: 268-274 |
| 1998 |
|---|
| 9 | | Maria Luisa Bonet,
Juan Luis Esteban,
Nicola Galesi,
Jan Johannsen:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems.
FOCS 1998: 638-647 |
| 8 |  | Jan Johannsen,
Chris Pollett:
On Proofs about Threshold Circuits and Counting Hierarchies.
LICS 1998: 444-452 |
| 7 | | Maria Luisa Bonet,
Juan Luis Esteban,
Nicola Galesi,
Jan Johannsen:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems
Electronic Colloquium on Computational Complexity (ECCC) 5(35): (1998) |
| 6 | | Jan Johannsen:
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes.
Inf. Process. Lett. 67(1): 37-41 (1998) |
| 5 | | Jan Johannsen:
A Model Theoretic Property of Sharply Bounded Formulae, with some Applications.
Math. Log. Q. 44: 205-215 (1998) |
| 4 | | Jan Johannsen:
A Remark an Independence Results for Sharply Bounded Arithmetic.
Math. Log. Q. 44: 568-570 (1998) |
| 1997 |
|---|
| 3 | | Jan Johannsen:
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes
Electronic Colloquium on Computational Complexity (ECCC) 4(32): (1997) |
| 1995 |
|---|
| 2 | | Jan Johannsen:
On Sharply Bounded Length Induction.
CSL 1995: 362-367 |
| 1993 |
|---|
| 1 | | Jan Johannsen:
On the Weakness of Sharply Bounded Polynomial Induction.
Kurt Gödel Colloquium 1993: 223-230 |
