List of on-line available papers of Jacobo Torán

 

 

On the resolution complexity of Graph non-Isomorphism
Authors: Jacobo Torán
Proceedings SAT Conference 2013.

Restricted space algorithms for isomorphism of bounded treewidth graphs
Authors: Bireswar Das, Jacobo Torán and Fabian Wagner
Proceedings 27th STACS 2010.

The complexity of Planar Graph Isomorphism
Authors: Jacobo Torán and Fabian Wagner
Bulletin of the EATCS (97) 2009.


Reductions to Graph Isomorphism
Authors: Jacobo Torán
Proceedings 27th FSTTCS Conference 158-157, 2007.

Isomorphism Testing: Perspectives and Open Problems
Authors: V. Arvind and Jacobo Torán
Bulletin of the EATCS (86) 2005.

Solvable Group Isomorphism is (almost) in NP \cap coNP
Authors: V. Arvind and Jacobo Torán
Proceedings 19th Computational Complexity Conference 2004, 91-104.

Space and Width in Propositional Resolution
Author: Jacobo Torán
Bulletin of the EATCS (83) 2004.

A combinatorial characterization of treelike resolution space
Authors: Juan Luis Esteban and Jacobo Torán
Information Processing Letters 87 (2003) 295-300.

Completeness results for graph isomorphism
Authors: Birgit Jenner, Johannes Köbler
Pierre McKenzie and Jacobo Torán
Journal of Computer and System Sciences 66 (2003) 549-566.
[Corrigendum]

Optimal proof systems imply complete sets for promise classes
Authors: Johannes Köbler, Jochen Messner and Jacobo Torán
Information and Computation 184 (2003) 71-92.

Space bounds for Resolution
Authors: Juan Luis Esteban and Jacobo Torán
Information and Computation 171 1 (2001) 84-97.

On the hardness of Graph Isomorphism
Author: Jacobo Torán
FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.

A note on the hardness of tree isomorphism
Authors: Birgit Jenner, Pierre McKenzie and Jacobo Torán
Proceedings Computational Complexity Conference 98

Optimal proof systems for Propositional Logic and complete sets
Authors: Jochen Messner, and Jacobo Torán
STACS 98

A Nonadaptive NC Checker for Permutation Group Intersection
Authors: V. Arvind and Jacobo Torán
Theoretical Computer Science 259 597-611, 2001

On Finding the Number of Graph Automorphisms
Authors: Robert Beals, Richard Chang, Bill Gasarch, and Jacobo Torán
The Chicago Journal of Theoretical Computer Science, 1999

The Complexity of Obtaining Solutions for Problems in NP and NL
Author: Birgit Jenner and Jacobo Torán
In Complexity Theory Retrospective 2, L. Hemaspaandra and
A. Selman (eds.), 1997 Springer Verlag

Computing functions with parallel queries to NP
[Corrigendum]
Authors: Birgit Jenner and Jacobo Torán
Theoretical Computer Science 141, 1995, 175-193

Graph Isomorphism is low for PP
Authors: Johannes Köbler, Uwe Schöning, and Jacobo Torán
Computational Complexity 2, 1994, 301-330

The complexity of algorithmic problems on succinct instances 

Authors: Jose Luis Balcazar, Antoni Lozano and Jacobo Toran                                     Plenum Press 1992                                                                                                  
Turing Machines with Few Accepting Computations and Low Sets for PP
Authors: Johannes Köbler, Uwe Schöning, Seinosuke Toda and Jacobo Torán
Journal of Computing and System Sciences 44, 1992, 272-286  

The Power of the Middle Bit
Authors: Frederic Green, Johannes Köbler, and Jacobo Torán
7th Structure in Complexity Conference 1992, 111-118

Complexity Classes Defined by Counting Quantifiers
Author: Jacobo Torán
Journal of the ACM 38, 1991, 753-774

Counting the Number of Solutions
Author: Jacobo Torán
Invited lecture, 15th MFCS Conference 1990, SV LNCS 452, 121-135