 | 2012 |
|---|
| 80 |       | Johannes Köbler,
Sebastian Kuhnert,
Oleg Verbitsky:
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
CoRR abs/1202.4406: (2012) |
| 79 | | Sebastian Kuhnert,
Johannes Köbler,
Osamu Watanabe:
Interval graph representation with given interval and intersection lengths.
Electronic Colloquium on Computational Complexity (ECCC) 19: 32 (2012) |
| 2011 |
|---|
| 78 | | Vikraman Arvind,
Johannes Köbler:
Canonizing Hypergraphs under Abelian Group Action.
COCOON 2011: 444-455 |
| 77 | | Olaf Beyersdorff,
Johannes Köbler,
Sebastian Müller:
Proof systems that take advice.
Inf. Comput. 209(3): 320-332 (2011) |
| 76 | | Johannes Köbler,
Sebastian Kuhnert,
Bastian Laubner,
Oleg Verbitsky:
Interval Graphs: Canonical Representations in Logspace.
SIAM J. Comput. 40(5): 1292-1315 (2011) |
| 2010 |
|---|
| 75 | | Vikraman Arvind,
Bireswar Das,
Johannes Köbler,
Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
FSTTCS 2010: 327-337 |
| 74 | | Johannes Köbler,
Sebastian Kuhnert,
Bastian Laubner,
Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace.
ICALP (1) 2010: 384-395 |
| 73 | | Johannes Köbler,
Sebastian Kuhnert,
Bastian Laubner,
Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace.
Electronic Colloquium on Computational Complexity (ECCC) 17: 43 (2010) |
| 2009 |
|---|
| 72 | | Olaf Beyersdorff,
Johannes Köbler,
Sebastian Müller:
Nondeterministic Instance Complexity and Proof Systems with Advice.
LATA 2009: 164-175 |
| 71 | | Johannes Köbler,
Sebastian Kuhnert:
The Isomorphism Problem for k-Trees Is Complete for Logspace.
MFCS 2009: 537-548 |
| 70 | | Johannes Köbler,
Sebastian Kuhnert:
The Isomorphism Problem for k-Trees is Complete for Logspace.
Electronic Colloquium on Computational Complexity (ECCC) 16: 53 (2009) |
| 69 | | Olaf Beyersdorff,
Johannes Köbler,
Sebastian Müller:
Proof Systems that Take Advice.
Electronic Colloquium on Computational Complexity (ECCC) 16: 92 (2009) |
| 68 | | Vikraman Arvind,
Bireswar Das,
Johannes Köbler,
Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
Electronic Colloquium on Computational Complexity (ECCC) 16: 93 (2009) |
| 67 | | Olaf Beyersdorff,
Johannes Köbler,
Jochen Messner:
Nondeterministic functions and the existence of optimal proof systems.
Theor. Comput. Sci. 410(38-40): 3839-3855 (2009) |
| 66 | | Vikraman Arvind,
Johannes Köbler,
Wolfgang Lindner:
Parameterized learnability of juntas.
Theor. Comput. Sci. 410(47-49): 4928-4936 (2009) |
| 2008 |
|---|
| 65 | | Johannes Köbler,
Oleg Verbitsky:
From Invariants to Canonization in Parallel.
CSR 2008: 216-227 |
| 64 | | Vikraman Arvind,
Bireswar Das,
Johannes Köbler:
A Logspace Algorithm for Partial 2-Tree Canonization.
CSR 2008: 40-51 |
| 63 | | Olaf Beyersdorff,
Johannes Köbler,
Sebastian Müller:
Nondeterministic Instance Complexity and Proof Systems with Advice.
Electronic Colloquium on Computational Complexity (ECCC) 15(075): (2008) |
| 2007 |
|---|
| 62 | | Vikraman Arvind,
Johannes Köbler,
Wolfgang Lindner:
Parameterized Learnability of k -Juntas and Related Problems.
ALT 2007: 120-134 |
| 61 | | Vikraman Arvind,
Bireswar Das,
Johannes Köbler:
The Space Complexity of k -Tree Isomorphism.
ISAAC 2007: 822-833 |
| 60 | | José L. Balcázar,
Jorge Castro,
David Guijarro,
Johannes Köbler,
Wolfgang Lindner:
A general dimension for query learning.
J. Comput. Syst. Sci. 73(6): 924-940 (2007) |
| 2006 |
|---|
| 59 | | Johannes Köbler:
On Graph Isomorphism for Restricted Graph Classes.
CiE 2006: 241-256 |
| 58 | | Vikraman Arvind,
Johannes Köbler:
On Hypergraph and Graph Isomorphism with Bounded Color Classes.
STACS 2006: 384-395 |
| 57 |  | Johannes Köbler,
Wolfgang Lindner:
Learning Boolean Functions under the Uniform.
Bulletin of the EATCS 89: 48-78 (2006) |
| 56 | | Johannes Köbler,
Oleg Verbitsky:
From Invariants to Canonization in Parallel
CoRR abs/cs/0608074: (2006) |
| 55 | | Birgit Jenner,
Johannes Köbler,
Pierre McKenzie,
Jacobo Torán:
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci. 72(4): 783 (2006) |
| 54 | | Johannes Köbler,
Wolfgang Lindner:
The complexity of learning concept classes with polynomial general dimension.
Theor. Comput. Sci. 350(1): 49-62 (2006) |
| 2004 |
|---|
| 53 | | Johannes Köbler,
Rainer Schuler:
Average-case intractability vs. worst-case intractability.
Inf. Comput. 190(1): 1-17 (2004) |
| 2003 |
|---|
| 52 | | Johannes Köbler,
Jochen Messner,
Jacobo Torán:
Optimal proof systems imply complete sets for promise classes.
Inf. Comput. 184(1): 71-92 (2003) |
| 51 | | Birgit Jenner,
Johannes Köbler,
Pierre McKenzie,
Jacobo Torán:
Completeness results for graph isomorphism.
J. Comput. Syst. Sci. 66(3): 549-566 (2003) |
| 2002 |
|---|
| 50 | | Johannes Köbler,
Wolfgang Lindner:
A General Dimension for Approximately Learning Boolean Functions.
ALT 2002: 139-148 |
| 49 | | Johannes Köbler,
Wolfgang Lindner:
The Complexity of Learning Concept Classes with Polynomial General Dimension.
ALT 2002: 149-163 |
| 48 | | Johannes Köbler,
Jacobo Torán:
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.
STACS 2002: 121-132 |
| 47 | | Vikraman Arvind,
Johannes Köbler:
New Lowness Results for ZPPNP and Other Complexity Classes.
J. Comput. Syst. Sci. 65(2): 257-277 (2002) |
| 2001 |
|---|
| 46 | | Vikraman Arvind,
Johannes Köbler:
On pseudorandomness and resource-bounded measure.
Theor. Comput. Sci. 255(1-2): 205-221 (2001) |
| 2000 |
|---|
| 45 | | Johannes Köbler,
Wolfgang Lindner:
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.
FSTTCS 2000: 336-347 |
| 44 | | Johannes Köbler,
Jochen Messner:
Is the Standard Proof System for SAT P-Optimal?
FSTTCS 2000: 361-372 |
| 43 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk,
Jacobo Torán:
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.
STACS 2000: 314-323 |
| 42 | | Vikraman Arvind,
Johannes Köbler:
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.
STACS 2000: 431-442 |
| 41 | | Johannes Köbler,
Wolfgang Lindner:
Oracles in Sp2 are Sufficient for Exact Learning.
Int. J. Found. Comput. Sci. 11(4): 615-632 (2000) |
| 1999 |
|---|
| 40 | | Christoph Karg,
Johannes Köbler,
Rainer Schuler:
The Complexity of Generating Test Instances.
Chicago J. Theor. Comput. Sci. 1999: (1999) |
| 39 | | Vikraman Arvind,
Johannes Köbler:
Graph Isomorphism is Low for ZPPNP and other Lowness results.
Electronic Colloquium on Computational Complexity (ECCC) 6(33): (1999) |
| 1998 |
|---|
| 38 | | Johannes Köbler,
Jochen Messner:
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.
IEEE Conference on Computational Complexity 1998: 132-140 |
| 37 | | Johannes Köbler,
Wolfgang Lindner:
On the Resource Bounded Measure of P/poly.
IEEE Conference on Computational Complexity 1998: 182-185 |
| 36 | | Johannes Köbler,
Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability.
MFCS 1998: 493-502 |
| 35 | | Johannes Köbler,
Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability
Electronic Colloquium on Computational Complexity (ECCC) 5(37): (1998) |
| 34 | | Johannes Köbler,
Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput. 28(1): 311-324 (1998) |
| 1997 |
|---|
| 33 | | Johannes Köbler,
Wolfgang Lindner:
Oracles in Sigmap2 are Sufficient for Exact Learning.
ALT 1997: 277-290 |
| 32 | | Johannes Köbler,
Uwe Schöning:
High Sets for NP.
Advances in Algorithms, Languages, and Complexity 1997: 139-156 |
| 31 | | Vikraman Arvind,
Johannes Köbler:
On Resource-Bounded Measure and Pseudorandomness.
FSTTCS 1997: 235-249 |
| 30 | | Christoph Karg,
Johannes Köbler,
Rainer Schuler:
The Complexity of Generating Test Instances.
STACS 1997: 375-386 |
| 1996 |
|---|
| 29 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
Monotonous and Randomized Reductions to Sparse Sets.
ITA 30(2): 155-179 (1996) |
| 28 | | Johannes Köbler,
Seinosuke Toda:
On the Power of Generalized MOD-Classes.
Mathematical Systems Theory 29(1): 33-46 (1996) |
| 27 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
Upper Bounds for the Complexity of Sparse and Tally Descriptions.
Mathematical Systems Theory 29(1): 63-94 (1996) |
| 1995 |
|---|
| 26 | | Johannes Köbler,
Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits.
ICALP 1995: 196-207 |
| 25 | | Johannes Köbler:
On the Structure of Low Sets.
Structure in Complexity Theory Conference 1995: 246-261 |
| 24 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
On Reductions to Sets that Avoid EXPSPACE.
Inf. Process. Lett. 56(2): 109-114 (1995) |
| 23 | | Vikraman Arvind,
Johannes Köbler,
Rainer Schuler:
On Helping and Interactive Proof Systems.
Int. J. Found. Comput. Sci. 6(2): 137-153 (1995) |
| 22 | | Frederic Green,
Johannes Köbler,
Kenneth W. Regan,
Thomas Schwentick,
Jacobo Torán:
The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci. 50(3): 456-467 (1995) |
| 21 | | Vikraman Arvind,
Johannes Köbler,
Uwe Schöning,
Rainer Schuler:
If NP has Polynomial-Size Circuits, then MA=AM.
Theor. Comput. Sci. 137(2): 279-282 (1995) |
| 1994 |
|---|
| 20 | | Vikraman Arvind,
Johannes Köbler,
Rainer Schuler:
On Helping and Interactive Proof Systems.
ISAAC 1994: 137-145 |
| 19 | | Johannes Köbler,
Thomas Thierauf:
Complexity-Restricted Advice Functions.
SIAM J. Comput. 23(2): 261-275 (1994) |
| 18 | | Johannes Köbler:
Locating P/poly Optimally in the Extended Low Hierarchy.
Theor. Comput. Sci. 134(2): 263-285 (1994) |
| 1993 |
|---|
| 17 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.
MFCS 1993: 232-241 |
| 16 | | Johannes Köbler:
Locating P/poly Optimally in the Extended Low Hierarchy.
STACS 1993: 28-37 |
| 15 | | Johannes Köbler,
Seinosuke Toda:
On the Power of Generalized MOD-Classes.
Structure in Complexity Theory Conference 1993: 147-155 |
| 1992 |
|---|
| 14 | | Vikraman Arvind,
Yenjo Han,
Lane A. Hemachandra,
Johannes Köbler,
Antoni Lozano,
Martin Mundhenk,
Mitsunori Ogiwara,
Uwe Schöning,
Riccardo Silvestri,
Thomas Thierauf:
Reductions to Sets of Low Information Content.
Complexity Theory: Current Research 1992: 1-46 |
| 13 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.
FSTTCS 1992: 140-151 |
| 12 | | Vikraman Arvind,
Yenjo Han,
Lane A. Hemachandra,
Johannes Köbler,
Antoni Lozano,
Martin Mundhenk,
Mitsunori Ogiwara,
Uwe Schöning,
Riccardo Silvestri,
Thomas Thierauf:
Reductions to Sets of Low Information Content.
ICALP 1992: 162-173 |
| 11 | | Vikraman Arvind,
Johannes Köbler,
Martin Mundhenk:
Lowness and the Complexity of Sparse and Tally Descriptions.
ISAAC 1992: 249-258 |
| 10 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
Graph Isomorphism is Low for PP.
STACS 1992: 401-411 |
| 9 | | Frederic Green,
Johannes Köbler,
Jacobo Torán:
The Power of the Middle Bit.
Structure in Complexity Theory Conference 1992: 111-117 |
| 8 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
Graph Isomorphism is Low for PP.
Computational Complexity 2: 301-330 (1992) |
| 7 | | Johannes Köbler,
Uwe Schöning,
Seinosuke Toda,
Jacobo Torán:
Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci. 44(2): 272-286 (1992) |
| 1990 |
|---|
| 6 | | Johannes Köbler,
Thomas Thierauf:
Complexity Classes with Advice.
Structure in Complexity Theory Conference 1990: 305-315 |
| 1989 |
|---|
| 5 | | Johannes Köbler,
Uwe Schöning,
Seinosuke Toda,
Jacobo Torán:
Turing Machines with few Accepting Computations and low Sets for PP.
Structure in Complexity Theory Conference 1989: 208-215 |
| 4 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
On Counting and Approximation.
Acta Inf. 26(4): 363-379 (1989) |
| 3 | | Johannes Köbler:
Strukturelle Komplexität von Anzahlproblemen.
Universität Stuttgart 1989: 1-83 |
| 1988 |
|---|
| 2 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
On Counting and Approximation.
CAAP 1988: 40-51 |
| 1987 |
|---|
| 1 | | Johannes Köbler,
Uwe Schöning,
Klaus W. Wagner:
The Difference and Truth-Table Hierarchies for NP.
ITA 21(4): 419-435 (1987) |
Data released under the ODC-BY 1.0 license — See also our legal information page