![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Jacobo Torán
Person information
- affiliation: University of Ulm, Institute of Theoretical Computer Science, Germany
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2012
- [b3]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 - 2009
- [b2]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 - 1993
- [b1]Johannes Köbler, Uwe Schöning, Jacobo Torán:
The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science, Birkhäuser/Springer 1993, ISBN 978-1-4612-6712-6
Journal Articles
- 2023
- [j37]Julian Nickerl
, Jacobo Torán:
Pure Nash equilibria in a generalization of congestion games allowing resource failures. Theor. Comput. Sci. 963: 113933 (2023) - [j36]Jacobo Torán
, Florian Wörz
:
Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas. ACM Trans. Comput. Log. 24(3): 23:1-23:25 (2023) - 2021
- [j35]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms and Isomorphisms. Algorithmica 83(12): 3567-3601 (2021) - [j34]Jacobo Torán, Florian Wörz
:
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. Comput. Complex. 30(1): 7 (2021) - 2020
- [j33]Nicola Galesi, Navid Talebanfard
, Jacobo Torán:
Cops-Robber Games and the Resolution of Tseitin Formulas. ACM Trans. Comput. Theory 12(2): 9:1-9:22 (2020) - 2017
- [j32]Bireswar Das, Patrick Scharpfenecker, Jacobo Torán:
CNF and DNF succinct graph encodings. Inf. Comput. 253: 436-447 (2017) - 2016
- [j31]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert
, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. Algorithmica 75(2): 322-338 (2016) - [j30]Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. J. Satisf. Boolean Model. Comput. 10(1): 37-58 (2016) - 2015
- [j29]Johannes Köbler, Jacobo Torán:
Lowness results: the next generation. Bull. EATCS 117 (2015) - 2013
- [j28]Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner:
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism. ACM Trans. Comput. Theory 5(4): 13:1-13:13 (2013) - 2012
- [j27]Bireswar Das, Jacobo Torán, Fabian Wagner:
Restricted space algorithms for isomorphism on bounded treewidth graphs. Inf. Comput. 217: 71-83 (2012) - 2011
- [j26]Vikraman Arvind, Jacobo Torán:
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP. ACM Trans. Comput. Theory 2(2): 4:1-4:22 (2011) - 2010
- [j25]Jacobo Torán:
Reductions to Graph Isomorphism. Theory Comput. Syst. 47(1): 288-299 (2010) - 2009
- [j24]Jacobo Torán, Fabian Wagner:
The Complexity of Planar Graph Isomorphism. Bull. EATCS 97: 60-82 (2009) - 2006
- [j23]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) - 2005
- [j22]Vikraman Arvind, Jacobo Torán:
Isomorphism Testing: Perspective and Open Problems. Bull. EATCS 86: 66-84 (2005) - 2004
- [j21]Jacobo Torán:
Space and Width in Propositional Resolution (Column: Computational Complexity). Bull. EATCS 83: 86-104 (2004) - [j20]Jacobo Torán:
On the Hardness of Graph Isomorphism. SIAM J. Comput. 33(5): 1093-1108 (2004) - 2003
- [j19]Johannes Köbler, Jochen Messner, Jacobo Torán:
Optimal proof systems imply complete sets for promise classes. Inf. Comput. 184(1): 71-92 (2003) - [j18]Juan Luis Esteban
, Jacobo Torán:
A combinatorial characterization of treelike resolution space. Inf. Process. Lett. 87(6): 295-300 (2003) - [j17]Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán:
Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3): 549-566 (2003) - 2001
- [j16]Sven Baumer, Juan Luis Esteban, Jacobo Torán:
Minimally Unsatisfiable CNF Formulas. Bull. EATCS 74: 190-192 (2001) - [j15]Juan Luis Esteban
, Jacobo Torán:
Space Bounds for Resolution. Inf. Comput. 171(1): 84-97 (2001) - [j14]Vikraman Arvind, Jacobo Torán:
A nonadaptive NC checker for permutation group intersection. Theor. Comput. Sci. 259(1-2): 597-611 (2001) - 1999
- [j13]Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán:
On Finding the Number of Graph Automorphisms. Chic. J. Theor. Comput. Sci. 1999 (1999) - [j12]Vikraman Arvind, Jacobo Torán:
Sparse Sets, Approximable Sets, and Parallel Queries to NP. Inf. Process. Lett. 69(4): 181-188 (1999) - 1997
- [j11]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) - 1996
- [j10]Josep Díaz, Maria J. Serna, Jacobo Torán:
Parallel Approximation Schemes for Problems on Planar Graphs. Acta Informatica 33(4): 387-408 (1996) - 1995
- [j9]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) - [j8]Birgit Jenner, Jacobo Torán:
Computing Functions with Parallel Queries to NP. Theor. Comput. Sci. 141(1&2): 175-193 (1995) - 1992
- [j7]Johannes Köbler, Uwe Schöning, Jacobo Torán:
Graph Isomorphism is Low for PP. Comput. Complex. 2: 301-330 (1992) - [j6]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) - 1991
- [j5]Jacobo Torán:
Complexity Classes Defined by Counting Quantifiers. J. ACM 38(3): 753-774 (1991) - [j4]Antoni Lozano
, Jacobo Torán:
Self-Reducible Sets of Small Sensity. Math. Syst. Theory 24(2): 83-100 (1991) - 1990
- [j3]Josep Díaz
, Jacobo Torán:
Classes of Bounded Nondeterminism. Math. Syst. Theory 23(1): 21-32 (1990) - 1989
- [j2]Johannes Köbler, Uwe Schöning, Jacobo Torán:
On Counting and Approximation. Acta Informatica 26(4): 363-379 (1989) - 1987
- [j1]Jacobo Torán:
On The Complexity of Computable Real Sequences. RAIRO Theor. Informatics Appl. 21(2): 175-180 (1987)
Conference and Workshop Papers
- 2024
- [c44]Tobias Heß
, Sean Niklas Semmler
, Chico Sundermann
, Jacobo Torán, Thomas Thüm
:
Towards Deterministic Compilation of Binary Decision Diagrams From Feature Models. SPLC (A) 2024: 136-147 - 2023
- [c43]Jacobo Torán, Florian Wörz:
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations. SAT 2023: 26:1-26:20 - 2022
- [c42]Jacobo Torán, Florian Wörz
:
Number of Variables for Graph Differentiation and the Resolution of GI Formulas. CSL 2022: 36:1-36:18 - 2021
- [c41]Julian Nickerl
, Jacobo Torán
:
Pure Nash Equilibria in a Generalization of Congestion Games Allowing Resource Failures. SAGT 2021: 186-201 - 2020
- [c40]Jacobo Torán, Florian Wörz
:
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. STACS 2020: 60:1-60:18 - 2018
- [c39]Nicola Galesi, Navid Talebanfard
, Jacobo Torán:
Cops-Robber Games and the Resolution of Tseitin Formulas. SAT 2018: 311-326 - 2017
- [c38]Stefan Arnold, Jacobo Torán:
A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy. CiE 2017: 119-128 - [c37]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. IPEC 2017: 2:1-2:13 - [c36]Vikraman Arvind, Johannes Köbler
, Sebastian Kuhnert
, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms. STACS 2017: 7:1-7:13 - 2016
- [c35]Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. SAT 2016: 29-44 - 2014
- [c34]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert
, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. IPEC 2014: 39-50 - [c33]Bireswar Das, Patrick Scharpfenecker, Jacobo Torán:
Succinct Encodings of Graph Isomorphism. LATA 2014: 285-296 - 2013
- [c32]Jacobo Torán:
On the Resolution Complexity of Graph Non-isomorphism. SAT 2013: 52-66 - 2010
- [c31]Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner:
Graph Isomorphism is not AC^0 reducible to Group Isomorphism. FSTTCS 2010: 317-326 - [c30]Bireswar Das, Jacobo Torán, Fabian Wagner:
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. STACS 2010: 227-238 - 2007
- [c29]Jacobo Torán:
Reductions to Graph Isomorphism. FSTTCS 2007: 158-167 - 2006
- [c28]Vikraman Arvind, Jacobo Torán:
The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem. ISAAC 2006: 233-242 - 2005
- [c27]Jacobo Torán:
Arthur-Merlin Games and the Problem of Isomorphism Testing. CiE 2005: 495-506 - 2004
- [c26]Vikraman Arvind, Jacobo Torán:
Solvable Group Isomorphism. CCC 2004: 91-103 - 2002
- [c25]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 - 2000
- [c24]Jacobo Torán:
On the Hardness of Graph Isomorphism. FOCS 2000: 180-186 - [c23]Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán:
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. STACS 2000: 314-323 - 1999
- [c22]Jacobo Torán:
Lower Bounds for Space in Resolution. CSL 1999: 362-373 - [c21]Vikraman Arvind, Jacobo Torán:
Sparse Sets, Approximable Sets, and Parallel Queries to NP. STACS 1999: 281-290 - [c20]Juan Luis Esteban
, Jacobo Torán:
Space Bounds for Resolution. STACS 1999: 551-560 - 1998
- [c19]Birgit Jenner, Pierre McKenzie, Jacobo Torán:
A Note on the Hardness of Tree Isomorphism. CCC 1998: 101-105 - [c18]Jochen Meßner, Jacobo Torán:
Optimal Proof Systems for Propositional Logic and Complete Sets. STACS 1998: 477-487 - 1997
- [c17]Vikraman Arvind, Jacobo Torán:
A Nonadaptive NC Checker for Permutation Group Intersection. CCC 1997: 204-212 - 1995
- [c16]Richard Chang, William I. Gasarch, Jacobo Torán:
On Finding the Number of Graph Automorphisms. SCT 1995: 288-298 - [c15]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 - 1993
- [c14]Birgit Jenner, Jacobo Torán:
Computing Functions with Parallel Queries to NP. SCT 1993: 280-291 - [c13]Josep Díaz, Maria J. Serna, Jacobo Torán:
Parallel Approximation Schemes for problems on planar graphs (Extended Abstract). ESA 1993: 145-156 - 1992
- [c12]Frederic Green, Johannes Köbler, Jacobo Torán:
The Power of the Middle Bit. SCT 1992: 111-117 - [c11]Antoni Lozano, Jacobo Torán:
On the Nonuniform Complexity on the Graph Isomorphism Problem. SCT 1992: 118-129 - [c10]Antoni Lozano, Jacobo Torán:
On the Non-Uniform Complexity of the Graph Isomorphism Problem. Complexity Theory: Current Research 1992: 245-271 - [c9]Johannes Köbler, Uwe Schöning, Jacobo Torán:
Graph Isomorphism is Low for PP. STACS 1992: 401-411 - 1991
- [c8]Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán:
The MINSUMCUT Problem. WADS 1991: 65-89 - 1990
- [c7]Jacobo Torán:
Counting the Number of Solutions. MFCS 1990: 121-134 - 1989
- [c6]Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán:
Turing Machines with few Accepting Computations and low Sets for PP. SCT 1989: 208-215 - [c5]Carme Àlvarez, Josep Díaz, Jacobo Torán:
Complexity Classes with Complete Problems Between P and NP-C. FCT 1989: 13-24 - [c4]Jacobo Torán:
A Combinatorial Technique for Separating Counting Complexity Classes. ICALP 1989: 733-744 - 1988
- [c3]Jacobo Torán:
Succinct Representations of Counting Problems. AAECC 1988: 415-426 - [c2]Johannes Köbler, Uwe Schöning, Jacobo Torán:
On Counting and Approximation. CAAP 1988: 40-51 - [c1]Jacobo Torán:
An oracle characterization of the counting hierarchy. SCT 1988: 213-223
Informal and Other Publications
- 2024
- [i23]Lisa Jaser, Jacobo Torán:
Pebble Games and Algebraic Proof Systems Meet Again. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [i22]Jacobo Torán, Florian Wörz:
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i21]Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán:
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). Dagstuhl Reports 12(9): 41-59 (2022) - 2021
- [i20]Jacobo Torán, Florian Wörz
:
Number of Variables for Graph Identification and the Resolution of GI Formulas. Electron. Colloquium Comput. Complex. TR21 (2021) - 2019
- [i19]Jacobo Torán, Florian Wörz
:
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i18]Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports 8(9): 133-153 (2018) - [i17]Nicola Galesi, Navid Talebanfard, Jacobo Torán:
Cops-Robber games and the resolution of Tseitin formulas. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i16]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. CoRR abs/1709.10063 (2017) - 2016
- [i15]Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports 6(10): 13-32 (2016) - [i14]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms. Electron. Colloquium Comput. Complex. TR16 (2016) - [i13]Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i12]László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán:
The Graph Isomorphism Problem (Dagstuhl Seminar 15511). Dagstuhl Reports 5(12): 1-17 (2015) - [i11]Bireswar Das, Patrick Scharpfenecker, Jacobo Torán:
Succinct Encodings of Graph Isomorphism. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i10]Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. Electron. Colloquium Comput. Complex. TR14 (2014) - 2010
- [i9]Bireswar Das, Jacobo Torán, Fabian Wagner:
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. CoRR abs/1001.0383 (2010) - [i8]Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner:
Graph Isomorphism is not AC^0 reducible to Group Isomorphism. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i7]Bireswar Das, Jacobo Torán, Fabian Wagner:
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. Electron. Colloquium Comput. Complex. TR09 (2009) - 2007
- [i6]Jacobo Torán:
Reductions to Graph Isomorphism. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i5]Uwe Schöning, Jacobo Torán:
A note on the size of Craig Interpolants. Circuits, Logic, and Games 2006 - 2004
- [i4]Vikraman Arvind, Jacobo Torán:
Solvable Group Isomorphism is (almost) in NP\cap coNP. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [i3]Juan Luis Esteban, Jacobo Torán:
A Combinatorial Characterization of Treelike Resolution Space. Electron. Colloquium Comput. Complex. TR03 (2003) - 1998
- [i2]Vikraman Arvind, Jacobo Torán:
Sparse Sets, Approximable Sets, and Parallel Queries to NP. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [i1]Jochen Meßner, Jacobo Torán:
Optimal proof systems for Propositional Logic and complete sets. Electron. Colloquium Comput. Complex. TR97 (1997)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-23 19:20 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint