Jacobo Torán

111 papers A* 2A 17B 10C 3Misc 1Journal 62Unranked 13
YearRankTypeTitle / Venue / Authors
2025 J jnl
Pebble Games and Algebraic Proof Systems.
CoRR
Lisa-Marie Jaser, Jacobo Torán
2024 J jnl
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381).
Dagstuhl Reports
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, Jacobo Torán, Kilian Rothmund
2024 J jnl
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations.
ACM Trans. Comput. Log.
Jacobo Torán, Florian Wörz
2024 J jnl
Pebble Games and Algebraic Proof Systems Meet Again.
Electron. Colloquium Comput. Complex.
Lisa-Marie Jaser, Jacobo Torán
2024 B conf
Pebble Games and Algebraic Proof Systems.
MFCS
Lisa-Marie Jaser, Jacobo Torán
2024 — conf
Towards Deterministic Compilation of Binary Decision Diagrams From Feature Models.
SPLC (A)
Tobias Heß, Sean Niklas Semmler, Chico Sundermann, Jacobo Torán, Thomas Thüm
2023 A conf
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations.
SAT
Jacobo Torán, Florian Wörz
2023 J jnl
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations.
Electron. Colloquium Comput. Complex.
Jacobo Torán, Florian Wörz
2023 J jnl
Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas.
ACM Trans. Comput. Log.
Jacobo Torán, Florian Wörz
2023 J jnl
Pure Nash equilibria in a generalization of congestion games allowing resource failures.
Theor. Comput. Sci.
Julian Nickerl, Jacobo Torán
2022 J jnl
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371).
Dagstuhl Reports
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán
2022 B conf
Number of Variables for Graph Differentiation and the Resolution of GI Formulas.
CSL
Jacobo Torán, Florian Wörz
2021 J jnl
Number of Variables for Graph Identification and the Resolution of GI Formulas.
Electron. Colloquium Comput. Complex.
Jacobo Torán, Florian Wörz
2021 J jnl
Parameterized Complexity of Small Weight Automorphisms and Isomorphisms.
Algorithmica
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2021 B conf
Pure Nash Equilibria in a Generalization of Congestion Games Allowing Resource Failures.
SAGT
Julian Nickerl, Jacobo Torán
2021 J jnl
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space.
Comput. Complex.
Jacobo Torán, Florian Wörz
2020 J jnl
Cops-Robber Games and the Resolution of Tseitin Formulas.
ACM Trans. Comput. Theory
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2020 A conf
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space.
STACS
Jacobo Torán, Florian Wörz
2019 J jnl
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space.
Electron. Colloquium Comput. Complex.
Jacobo Torán, Florian Wörz
2018 J jnl
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).
Dagstuhl Reports
Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans
2018 A conf
Cops-Robber Games and the Resolution of Tseitin Formulas.
SAT
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2018 J jnl
Cops-Robber games and the resolution of Tseitin formulas.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Navid Talebanfard, Jacobo Torán
2017 C conf
A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy.
CiE
Stefan Arnold, Jacobo Torán
2017 J jnl
CNF and DNF succinct graph encodings.
Inf. Comput.
Bireswar Das, Patrick Scharpfenecker, Jacobo Torán
2017 B conf
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
IPEC
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2017 J jnl
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
CoRR
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2017 A conf
Parameterized Complexity of Small Weight Automorphisms.
STACS
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2016 J jnl
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).
Dagstuhl Reports
Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans
2016 J jnl
Parameterized Complexity of Small Weight Automorphisms.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2016 A conf
Solution-Graphs of Boolean Formulas and Isomorphism.
SAT
Patrick Scharpfenecker, Jacobo Torán
2016 J jnl
Solution-Graphs of Boolean Formulas and Isomorphism.
Electron. Colloquium Comput. Complex.
Patrick Scharpfenecker, Jacobo Torán
2016 J jnl
Solution-Graphs of Boolean Formulas and Isomorphism.
J. Satisf. Boolean Model. Comput.
Patrick Scharpfenecker, Jacobo Torán
2016 J jnl
Solving Linear Equations Parameterized by Hamming Weight.
Algorithmica
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2015 J jnl
Lowness results: the next generation.
Bull. EATCS
Johannes Köbler, Jacobo Torán
2015 J jnl
Succinct Encodings of Graph Isomorphism.
Electron. Colloquium Comput. Complex.
Bireswar Das, Patrick Scharpfenecker, Jacobo Torán
2015 J jnl
The Graph Isomorphism Problem (Dagstuhl Seminar 15511).
Dagstuhl Reports
László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán
2014 B conf
Solving Linear Equations Parameterized by Hamming Weight.
IPEC
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2014 J jnl
Solving Linear Equations Parameterized by Hamming Weight.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán
2014 C conf
Succinct Encodings of Graph Isomorphism.
LATA
Bireswar Das, Patrick Scharpfenecker, Jacobo Torán
2013 J jnl
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism.
ACM Trans. Comput. Theory
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
2013 A conf
On the Resolution Complexity of Graph Non-isomorphism.
SAT
Jacobo Torán
2012 — book
Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen.
Uwe Schöning, Jacobo Torán
2012 J jnl
Restricted space algorithms for isomorphism on bounded treewidth graphs.
Inf. Comput.
Bireswar Das, Jacobo Torán, Fabian Wagner
2011 J jnl
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP.
ACM Trans. Comput. Theory
Vikraman Arvind, Jacobo Torán
2010 — conf
Graph Isomorphism is not AC^0 reducible to Group Isomorphism.
FSTTCS
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
2010 J jnl
Graph Isomorphism is not AC^0 reducible to Group Isomorphism.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
2010 J jnl
Reductions to Graph Isomorphism.
Theory Comput. Syst.
Jacobo Torán
2010 J jnl
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
CoRR
Bireswar Das, Jacobo Torán, Fabian Wagner
2010 A conf
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.
STACS
Bireswar Das, Jacobo Torán, Fabian Wagner
2009 — book
Paradigms for fast parallel approximability (Reprint from 1997).
Josep Díaz, Maria J. Serna, Paul G. Spirakis, Jacobo Torán
2009 J jnl
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.
Electron. Colloquium Comput. Complex.
Bireswar Das, Jacobo Torán, Fabian Wagner
2009 J jnl
The Complexity of Planar Graph Isomorphism.
Bull. EATCS
Jacobo Torán, Fabian Wagner
2007 — conf
Reductions to Graph Isomorphism.
FSTTCS
Jacobo Torán
2007 J jnl
Reductions to Graph Isomorphism.
Electron. Colloquium Comput. Complex.
Jacobo Torán
2006 — conf
A note on the size of Craig Interpolants.
Circuits, Logic, and Games
Uwe Schöning, Jacobo Torán
2006 J jnl
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2006 B conf
The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem.
ISAAC
Vikraman Arvind, Jacobo Torán
2005 C conf
Arthur-Merlin Games and the Problem of Isomorphism Testing.
CiE
Jacobo Torán
2005 J jnl
Isomorphism Testing: Perspective and Open Problems.
Bull. EATCS
Vikraman Arvind, Jacobo Torán
2004 J jnl
On the Hardness of Graph Isomorphism.
SIAM J. Comput.
Jacobo Torán
2004 J jnl
Solvable Group Isomorphism is (almost) in NP\cap coNP
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Jacobo Torán
2004 A conf
Solvable Group Isomorphism.
CCC
Vikraman Arvind, Jacobo Torán
2004 J jnl
Space and Width in Propositional Resolution (Column: Computational Complexity).
Bull. EATCS
Jacobo Torán
2003 J jnl
A Combinatorial Characterization of Treelike Resolution Space
Electron. Colloquium Comput. Complex.
Juan Luis Esteban, Jacobo Torán
2003 J jnl
A combinatorial characterization of treelike resolution space.
Inf. Process. Lett.
Juan Luis Esteban, Jacobo Torán
2003 J jnl
Completeness results for graph isomorphism.
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2003 J jnl
Optimal proof systems imply complete sets for promise classes.
Inf. Comput.
Johannes Köbler, Jochen Messner, Jacobo Torán
2002 A conf
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.
STACS
Johannes Köbler, Jacobo Torán
2001 J jnl
A nonadaptive NC checker for permutation group intersection.
Theor. Comput. Sci.
Vikraman Arvind, Jacobo Torán
2001 J jnl
Minimally Unsatisfiable CNF Formulas.
Bull. EATCS
Sven Baumer, Juan Luis Esteban, Jacobo Torán
2001 J jnl
Space Bounds for Resolution.
Inf. Comput.
Juan Luis Esteban, Jacobo Torán
2000 A conf
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.
STACS
Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán
2000 A* conf
On the Hardness of Graph Isomorphism.
FOCS
Jacobo Torán
1999 B conf
Lower Bounds for Space in Resolution.
CSL
Jacobo Torán
1999 J jnl
On Finding the Number of Graph Automorphisms.
Chic. J. Theor. Comput. Sci.
Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán
1999 A conf
Space Bounds for Resolution.
STACS
Juan Luis Esteban, Jacobo Torán
1999 A conf
Sparse Sets, Approximable Sets, and Parallel Queries to NP.
STACS
Vikraman Arvind, Jacobo Torán
1999 J jnl
Sparse Sets, Approximable Sets, and Parallel Queries to NP.
Inf. Process. Lett.
Vikraman Arvind, Jacobo Torán
1998 A conf
A Note on the Hardness of Tree Isomorphism.
CCC
Birgit Jenner, Pierre McKenzie, Jacobo Torán
1998 A conf
Optimal Proof Systems for Propositional Logic and Complete Sets.
STACS
Jochen Meßner, Jacobo Torán
1998 J jnl
Sparse Sets, Approximable Sets, and Parallel Queries to NP
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Jacobo Torán
1997 A conf
A Nonadaptive NC Checker for Permutation Group Intersection.
CCC
Vikraman Arvind, Jacobo Torán
1997 J jnl
Optimal proof systems for Propositional Logic and complete sets
Electron. Colloquium Comput. Complex.
Jochen Meßner, Jacobo Torán
1997 J jnl
Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems.
Theor. Comput. Sci.
Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán
1996 J jnl
Parallel Approximation Schemes for Problems on Planar Graphs.
Acta Informatica
Josep Díaz, Maria J. Serna, Jacobo Torán
1995 J jnl
Computing Functions with Parallel Queries to NP.
Theor. Comput. Sci.
Birgit Jenner, Jacobo Torán
1995 Misc conf
Efficient Parallel Algorithms for some Tree Layout Problems.
COCOON
Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán
1995 — conf
On Finding the Number of Graph Automorphisms.
SCT
Richard Chang, William I. Gasarch, Jacobo Torán
1995 J jnl
The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci.
Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán
1993 — conf
Computing Functions with Parallel Queries to NP.
SCT
Birgit Jenner, Jacobo Torán
1993 A conf
Parallel Approximation Schemes for problems on planar graphs (Extended Abstract).
ESA
Josep Díaz, Maria J. Serna, Jacobo Torán
1993 — book
The Graph Isomorphism Problem: Its Structural Complexity
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 A conf
Graph Isomorphism is Low for PP.
STACS
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 J jnl
Graph Isomorphism is Low for PP.
Comput. Complex.
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 — conf
On the Non-Uniform Complexity of the Graph Isomorphism Problem.
Complexity Theory: Current Research
Antoni Lozano, Jacobo Torán
1992 — conf
On the Nonuniform Complexity on the Graph Isomorphism Problem.
SCT
Antoni Lozano, Jacobo Torán
1992 — conf
The Power of the Middle Bit.
SCT
Frederic Green, Johannes Köbler, Jacobo Torán
1992 J jnl
Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci.
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán
1991 J jnl
Complexity Classes Defined by Counting Quantifiers.
J. ACM
Jacobo Torán
1991 J jnl
Self-Reducible Sets of Small Sensity.
Math. Syst. Theory
Antoni Lozano, Jacobo Torán
1991 B conf
The MINSUMCUT Problem.
WADS
Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán
1990 J jnl
Classes of Bounded Nondeterminism.
Math. Syst. Theory
Josep Díaz, Jacobo Torán
1990 B conf
Counting the Number of Solutions.
MFCS
Jacobo Torán
1989 A* conf
A Combinatorial Technique for Separating Counting Complexity Classes.
ICALP
Jacobo Torán
1989 B conf
Complexity Classes with Complete Problems Between P and NP-C.
FCT
Carme Àlvarez, Josep Díaz, Jacobo Torán
1989 J jnl
On Counting and Approximation.
Acta Informatica
Johannes Köbler, Uwe Schöning, Jacobo Torán
1989 — conf
Turing Machines with few Accepting Computations and low Sets for PP.
SCT
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán
1988 — conf
An oracle characterization of the counting hierarchy.
SCT
Jacobo Torán
1988 — conf
On Counting and Approximation.
CAAP
Johannes Köbler, Uwe Schöning, Jacobo Torán
1988 — conf
Succinct Representations of Counting Problems.
AAECC
Jacobo Torán
1987 J jnl
On The Complexity of Computable Real Sequences.
RAIRO Theor. Informatics Appl.
Jacobo Torán