Jacobo Torán

Uwe Schöning, Jacobo Torán: Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen. Mathematik für Anwendungen 1, Lehmann 2012, isbn 978-3-86541-473-1, pp. 1-187

Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted space algorithms for isomorphism on bounded treewidth graphs. Inf. Comput. 217: 71-83 (2012)

Vikraman Arvind, Jacobo Torán: Solvable Group Isomorphism Is (Almost) in NP ∩ coNP. TOCT 2(2): 4 (2011)

Jacobo Torán: Reductions to Graph Isomorphism. Theory Comput. Syst. 47(1): 288-299 (2010)

Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph Isomorphism is not AC^0 reducible to Group Isomorphism. FSTTCS 2010: 317-326

Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. STACS 2010: 227-238

Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. CoRR abs/1001.0383 (2010)

Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph Isomorphism is not AC^0 reducible to Group Isomorphism. Electronic Colloquium on Computational Complexity (ECCC) 17: 117 (2010)

Josep Díaz, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Paradigms for fast parallel approximability (Reprint from 1997). Cambridge international series on parallel computation 8, Cambridge University Press 2009, isbn 978-0-521-43170-5, pp. I-VIII, 1-158

Jacobo Torán, Fabian Wagner: The Complexity of Planar Graph Isomorphism. Bulletin of the EATCS 97: 60-82 (2009)

Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. Electronic Colloquium on Computational Complexity (ECCC) 16: 94 (2009)

Jacobo Torán: Reductions to Graph Isomorphism. FSTTCS 2007: 158-167

Jacobo Torán: Reductions to Graph Isomorphism. Electronic Colloquium on Computational Complexity (ECCC) 14(071) (2007)

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)

Uwe Schöning, Jacobo Torán: A note on the size of Craig Interpolants. Circuits, Logic, and Games 2006

Vikraman Arvind, Jacobo Torán: The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem. ISAAC 2006: 233-242

Vikraman Arvind, Jacobo Torán: Isomorphism Testing: Perspective and Open Problems. Bulletin of the EATCS 86: 66-84 (2005)

Jacobo Torán: Arthur-Merlin Games and the Problem of Isomorphism Testing. CiE 2005: 495-506

Jacobo Torán: Space and Width in Propositional Resolution (Column: Computational Complexity). Bulletin of the EATCS 83: 86-104 (2004)

Jacobo Torán: On the Hardness of Graph Isomorphism. SIAM J. Comput. 33(5): 1093-1108 (2004)

Vikraman Arvind, Jacobo Torán: Solvable Group Isomorphism. IEEE Conference on Computational Complexity 2004: 91-103

Vikraman Arvind, Jacobo Torán: Solvable Group Isomorphism is (almost) in NP\cap coNP. Electronic Colloquium on Computational Complexity (ECCC)(008) (2004)

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

Juan Luis Esteban, Jacobo Torán: A combinatorial characterization of treelike resolution space. Inf. Process. Lett. 87(6): 295-300 (2003)

Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán: Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3): 549-566 (2003)

Juan Luis Esteban, Jacobo Torán: A Combinatorial Characterization of Treelike Resolution Space. Electronic Colloquium on Computational Complexity (ECCC)(044) (2003)

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

S. Baumer, Juan Luis Esteban, Jacobo Torán: Minimally Unsatisfiable CNF Formulas. Bulletin of the EATCS 74: 190-192 (2001)

Juan Luis Esteban, Jacobo Torán: Space Bounds for Resolution. Inf. Comput. 171(1): 84-97 (2001)

Vikraman Arvind, Jacobo Torán: A nonadaptive NC checker for permutation group intersection. Theor. Comput. Sci. 259(1-2): 597-611 (2001)

Jacobo Torán: On the Hardness of Graph Isomorphism. FOCS 2000: 180-186

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán: Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. STACS 2000: 314-323

Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán: On Finding the Number of Graph Automorphisms. Chicago J. Theor. Comput. Sci. 1999 (1999)

Vikraman Arvind, Jacobo Torán: Sparse Sets, Approximable Sets, and Parallel Queries to NP. Inf. Process. Lett. 69(4): 181-188 (1999)

Jacobo Torán: Lower Bounds for Space in Resolution. CSL 1999: 362-373

Vikraman Arvind, Jacobo Torán: Sparse Sets, Approximable Sets, and Parallel Queries to NP. STACS 1999: 281-290

Juan Luis Esteban, Jacobo Torán: Space Bounds for Resolution. STACS 1999: 551-560

Birgit Jenner, Pierre McKenzie, Jacobo Torán: A Note on the Hardness of Tree Isomorphism. IEEE Conference on Computational Complexity 1998: 101-105

Jochen Meßner, Jacobo Torán: Optimal Proof Systems for Propositional Logic and Complete Sets. STACS 1998: 477-487

Vikraman Arvind, Jacobo Torán: Sparse Sets, Approximable Sets, and Parallel Queries to NP. Electronic Colloquium on Computational Complexity (ECCC) 5(27) (1998)

Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems. Theor. Comput. Sci. 181(2): 267-287 (1997)

Vikraman Arvind, Jacobo Torán: A Nonadaptive NC Checker for Permutation Group Intersection. IEEE Conference on Computational Complexity 1997: 204-212

Jochen Meßner, Jacobo Torán: Optimal proof systems for Propositional Logic and complete sets. Electronic Colloquium on Computational Complexity (ECCC) 4(26) (1997)

Josep Díaz, Maria J. Serna, Jacobo Torán: Parallel Approximation Schemes for Problems on Planar Graphs. Acta Inf. 33(4): 387-408 (1996)

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)

Birgit Jenner, Jacobo Torán: Computing Functions with Parallel Queries to NP. Theor. Comput. Sci. 141(1&2): 175-193 (1995)

Richard Chang, William I. Gasarch, Jacobo Torán: On Finding the Number of Graph Automorphisms. Structure in Complexity Theory Conference 1995: 288-298

Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Efficient Parallel Algorithms for some Tree Layout Problems. COCOON 1995: 313-323

Birgit Jenner, Jacobo Torán: Computing Functions with Parallel Queries to NP. Structure in Complexity Theory Conference 1993: 280-291

Josep Díaz, Maria J. Serna, Jacobo Torán: Parallel Approximation Schemes for problems on planar graphs (Extended Abstract). ESA 1993: 145-156

Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. Computational Complexity 2: 301-330 (1992)

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)

Frederic Green, Johannes Köbler, Jacobo Torán: The Power of the Middle Bit. Structure in Complexity Theory Conference 1992: 111-117

Antoni Lozano, Jacobo Torán: On the Nonuniform Complexity on the Graph Isomorphism Problem. Structure in Complexity Theory Conference 1992: 118-129

Antoni Lozano, Jacobo Torán: On the Non-Uniform Complexity of the Graph Isomorphism Problem. Complexity Theory: Current Research 1992: 245-271

Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. STACS 1992: 401-411

Jacobo Torán: Complexity Classes Defined by Counting Quantifiers. J. ACM 38(3): 753-774 (1991)

Antoni Lozano, Jacobo Torán: Self-Reducible Sets of Small Sensity. Mathematical Systems Theory 24(2): 83-100 (1991)

Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán: The MINSUMCUT Problem. WADS 1991: 65-89

Josep Díaz, Jacobo Torán: Classes of Bounded Nondeterminism. Mathematical Systems Theory 23(1): 21-32 (1990)

Jacobo Torán: Counting the Number of Solutions. MFCS 1990: 121-134

Johannes Köbler, Uwe Schöning, Jacobo Torán: On Counting and Approximation. Acta Inf. 26(4): 363-379 (1989)

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

Carme Àlvarez, Josep Díaz, Jacobo Torán: Complexity Classes with Complete Problems Between P and NP-C. FCT 1989: 13-24

Jacobo Torán: A Combinatorial Technique for Separating Counting Complexity Classes. ICALP 1989: 733-744

Jacobo Torán: Succinct Representations of Counting Problems. AAECC 1988: 415-426

Johannes Köbler, Uwe Schöning, Jacobo Torán: On Counting and Approximation. CAAP 1988: 40-51

Jacobo Torán: An oracle characterization of the counting hierarchy. Structure in Complexity Theory Conference 1988: 213-223

Jacobo Torán: On The Complexity of Computable Real Sequences. ITA 21(2): 175-180 (1987)