# Jacobo Torán

According to our database1, Jacobo Torán authored at least 89 papers between 1987 and 2018.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
Cops-Robber games and the resolution of Tseitin formulas.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Cops-Robber Games and the Resolution of Tseitin Formulas.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

2017
CNF and DNF succinct graph encodings.
Inf. Comput., 2017

Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
CoRR, 2017

Parameterized Complexity of Small Weight Automorphisms.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy.
Proceedings of the Unveiling Dynamics and Complexity, 2017

2016
Solution-Graphs of Boolean Formulas and Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Parameterized Complexity of Small Weight Automorphisms.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).
Dagstuhl Reports, 2016

Solving Linear Equations Parameterized by Hamming Weight.
Algorithmica, 2016

Solution-Graphs of Boolean Formulas and Isomorphism.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

2015
Succinct Encodings of Graph Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Lowness results: the next generation.
Bulletin of the EATCS, 2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).
Dagstuhl Reports, 2015

2014
Solving Linear Equations Parameterized by Hamming Weight.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Succinct Encodings of Graph Isomorphism.
Proceedings of the Language and Automata Theory and Applications, 2014

Solving Linear Equations Parameterized by Hamming Weight.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism.
TOCT, 2013

On the Resolution Complexity of Graph Non-isomorphism.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2013, 2013

2012
Restricted space algorithms for isomorphism on bounded treewidth graphs.
Inf. Comput., 2012

Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen.
Mathematik für Anwendungen 1, Lehmann, ISBN: 978-3-86541-473-1, 2012

2011
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP.
TOCT, 2011

2010
Reductions to Graph Isomorphism.
Theory Comput. Syst., 2010

Graph Isomorphism is not AC^0 reducible to Group Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
CoRR, 2010

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Graph Isomorphism is not AC^0 reducible to Group Isomorphism.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2009

The Complexity of Planar Graph Isomorphism.
Bulletin of the EATCS, 2009

Paradigms for fast parallel approximability (Reprint from 1997).
Cambridge international series on parallel computation 8, Cambridge University Press, ISBN: 978-0-521-43170-5, 2009

2007
Reductions to Graph Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Reductions to Graph Isomorphism.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci., 2006

The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

A note on the size of Craig Interpolants.
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

2005
Isomorphism Testing: Perspective and Open Problems.
Bulletin of the EATCS, 2005

Arthur-Merlin Games and the Problem of Isomorphism Testing.
Proceedings of the New Computational Paradigms, 2005

2004
On the Hardness of Graph Isomorphism.
SIAM J. Comput., 2004

Solvable Group Isomorphism is (almost) in NP\cap coNP
Electronic Colloquium on Computational Complexity (ECCC), 2004

Space and Width in Propositional Resolution (Column: Computational Complexity).
Bulletin of the EATCS, 2004

Solvable Group Isomorphism.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003
Completeness results for graph isomorphism.
J. Comput. Syst. Sci., 2003

A combinatorial characterization of treelike resolution space.
Inf. Process. Lett., 2003

Optimal proof systems imply complete sets for promise classes.
Inf. Comput., 2003

A Combinatorial Characterization of Treelike Resolution Space
Electronic Colloquium on Computational Complexity (ECCC), 2003

2002
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001
A nonadaptive NC checker for permutation group intersection.
Theor. Comput. Sci., 2001

Space Bounds for Resolution.
Inf. Comput., 2001

Minimally Unsatisfiable CNF Formulas.
Bulletin of the EATCS, 2001

2000
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.
Proceedings of the STACS 2000, 2000

On the Hardness of Graph Isomorphism.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Sparse Sets, Approximable Sets, and Parallel Queries to NP.
Inf. Process. Lett., 1999

On Finding the Number of Graph Automorphisms.
Chicago J. Theor. Comput. Sci., 1999

Space Bounds for Resolution.
Proceedings of the STACS 99, 1999

Sparse Sets, Approximable Sets, and Parallel Queries to NP.
Proceedings of the STACS 99, 1999

Lower Bounds for Space in Resolution.
Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998
Sparse Sets, Approximable Sets, and Parallel Queries to NP
Electronic Colloquium on Computational Complexity (ECCC), 1998

Optimal Proof Systems for Propositional Logic and Complete Sets.
Proceedings of the STACS 98, 1998

A Note on the Hardness of Tree Isomorphism.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems.
Theor. Comput. Sci., 1997

Optimal proof systems for Propositional Logic and complete sets
Electronic Colloquium on Computational Complexity (ECCC), 1997

A Nonadaptive NC Checker for Permutation Group Intersection.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Parallel Approximation Schemes for Problems on Planar Graphs.
Acta Inf., 1996

1995
Computing Functions with Parallel Queries to NP.
Theor. Comput. Sci., 1995

The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci., 1995

Efficient Parallel Algorithms for some Tree Layout Problems.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

On Finding the Number of Graph Automorphisms.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1993
Parallel Approximation Schemes for problems on planar graphs (Extended Abstract).
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

Computing Functions with Parallel Queries to NP.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.
Computational Complexity, 1992

Graph Isomorphism is Low for PP.
Proceedings of the STACS 92, 1992

On the Non-Uniform Complexity of the Graph Isomorphism Problem.
Proceedings of the Complexity Theory: Current Research, 1992

On the Nonuniform Complexity on the Graph Isomorphism Problem.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

The Power of the Middle Bit.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Self-Reducible Sets of Small Sensity.
Mathematical Systems Theory, 1991

Complexity Classes Defined by Counting Quantifiers.
J. ACM, 1991

The MINSUMCUT Problem.
Proceedings of the Algorithms and Data Structures, 1991

1990
Classes of Bounded Nondeterminism.
Mathematical Systems Theory, 1990

Counting the Number of Solutions.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989
On Counting and Approximation.
Acta Inf., 1989

A Combinatorial Technique for Separating Counting Complexity Classes.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Complexity Classes with Complete Problems Between P and NP-C.
Proceedings of the Fundamentals of Computation Theory, 1989

Turing Machines with few Accepting Computations and low Sets for PP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
An oracle characterization of the counting hierarchy.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

On Counting and Approximation.
Proceedings of the CAAP '88, 1988

Succinct Representations of Counting Problems.
Proceedings of the Applied Algebra, 1988

1987
On The Complexity of Computable Real Sequences.
ITA, 1987