Jacobo Torán

Electron. Colloquium Comput. Complex., 2024

Towards Deterministic Compilation of Binary Decision Diagrams From Feature Models.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM International Systems and Software Product Line Conference, 2024

Pebble Games and Algebraic Proof Systems.

[BibT_eX]

[DOI]

Lisa-Marie Jaser

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2023

Pure Nash equilibria in a generalization of congestion games allowing resource failures.

[BibT_eX]

[DOI]

Julian Nickerl

Theor. Comput. Sci., 2023

Cutting Planes Width and the Complexity of Graph Isomorphism Refutations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

2022

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371).

[BibT_eX]

[DOI]

Dagstuhl Reports, September, 2022

Number of Variables for Graph Differentiation and the Resolution of GI Formulas.

[BibT_eX]

[DOI]

Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2021

Number of Variables for Graph Identification and the Resolution of GI Formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space.

[BibT_eX]

[DOI]

Comput. Complex., 2021

Parameterized Complexity of Small Weight Automorphisms and Isomorphisms.

[BibT_eX]

[DOI]

Algorithmica, 2021

2018

Cops-Robber games and the resolution of Tseitin formulas.

[BibT_eX]

[DOI]

Nicola Galesi

Navid Talebanfard

Electron. Colloquium Comput. Complex., 2018

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2018

2017

CNF and DNF succinct graph encodings.

[BibT_eX]

[DOI]

Bireswar Das

Patrick Scharpfenecker

Inf. Comput., 2017

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Stefan Arnold

Proceedings of the Unveiling Dynamics and Complexity, 2017

2016

Solution-Graphs of Boolean Formulas and Isomorphism.

[BibT_eX]

[DOI]

Patrick Scharpfenecker

J. Satisf. Boolean Model. Comput., 2016

Parameterized Complexity of Small Weight Automorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

2015

Succinct Encodings of Graph Isomorphism.

[BibT_eX]

[DOI]

Bireswar Das

Patrick Scharpfenecker

Electron. Colloquium Comput. Complex., 2015

Lowness results: the next generation.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

2014

Solving Linear Equations Parameterized by Hamming Weight.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Graph Isomorphism is Not AC0-Reducible to Group Isomorphism.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

ACM Trans. Comput. Theory, 2013

On the Resolution Complexity of Graph Non-isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2013, 2013

2012

Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen.

[BibT_eX]

[DOI]

Mathematik für Anwendungen 1, Lehmann, ISBN: 978-3-86541-473-1, 2012

2011

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2011

2010

Graph Isomorphism is not AC^0 reducible to Group Isomorphism.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2010

2009

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Bireswar Das

Electron. Colloquium Comput. Complex., 2009

The Complexity of Planar Graph Isomorphism.

[BibT_eX]

Bull. EATCS, 2009

Paradigms for fast parallel approximability (Reprint from 1997).

[BibT_eX]

[DOI]

Cambridge international series on parallel computation 8, Cambridge University Press, ISBN: 978-0-521-43170-5, 2009

2007

Reductions to Graph Isomorphism.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

A note on the size of Craig Interpolants.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

2005

Isomorphism Testing: Perspective and Open Problems.

[BibT_eX]

Bull. EATCS, 2005

Arthur-Merlin Games and the Problem of Isomorphism Testing.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

On the Hardness of Graph Isomorphism.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Solvable Group Isomorphism is (almost) in NP\cap coNP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Space and Width in Propositional Resolution (Column: Computational Complexity).

[BibT_eX]

Bull. EATCS, 2004

Solvable Group Isomorphism.

[BibT_eX]

[DOI]

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

2003

Completeness results for graph isomorphism.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

A combinatorial characterization of treelike resolution space.

[BibT_eX]

[DOI]

Juan Luis Esteban

Inf. Process. Lett., 2003

Optimal proof systems imply complete sets for promise classes.

[BibT_eX]

[DOI]

Jochen Messner

Inf. Comput., 2003

2002

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Space Bounds for Resolution.

[BibT_eX]

[DOI]

Juan Luis Esteban

Inf. Comput., 2001

Minimally Unsatisfiable CNF Formulas.

[BibT_eX]

Sven Baumer

Juan Luis Esteban

Bull. EATCS, 2001

2000

Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

1999

Sparse Sets, Approximable Sets, and Parallel Queries to NP.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

On Finding the Number of Graph Automorphisms.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1999

Lower Bounds for Space in Resolution.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998

A Note on the Hardness of Tree Isomorphism.

[BibT_eX]

[DOI]

Birgit Jenner

Pierre McKenzie

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Optimal proof systems for Propositional Logic and complete sets

[BibT_eX]

[DOI]

Jochen Meßner

Electron. Colloquium Comput. Complex., 1997

1996

Parallel Approximation Schemes for Problems on Planar Graphs.

[BibT_eX]

[DOI]

Maria J. Serna

Acta Informatica, 1996

1995

Computing Functions with Parallel Queries to NP.

[BibT_eX]

[DOI]

Birgit Jenner

Theor. Comput. Sci., 1995

The Power of the Middle Bit of a #P Function.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

Efficient Parallel Algorithms for some Tree Layout Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

On Finding the Number of Graph Automorphisms.

[BibT_eX]

[DOI]

Richard Chang

William I. Gasarch

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1993

Parallel Approximation Schemes for problems on planar graphs (Extended Abstract).

[BibT_eX]

[DOI]

Maria J. Serna

Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

The Graph Isomorphism Problem: Its Structural Complexity

[BibT_eX]

[DOI]

Progress in Theoretical Computer Science, Birkhäuser/Springer, ISBN: 978-1-4612-0333-9, 1993

1992

Turing Machines with Few Accepting Computations and Low Sets for PP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.

[BibT_eX]

[DOI]

Comput. Complex., 1992

On the Non-Uniform Complexity of the Graph Isomorphism Problem.

[BibT_eX]

Antoni Lozano

Proceedings of the Complexity Theory: Current Research, 1992

On the Nonuniform Complexity on the Graph Isomorphism Problem.

[BibT_eX]

[DOI]

Antoni Lozano

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

The Power of the Middle Bit.

[BibT_eX]

[DOI]

Frederic Green

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Self-Reducible Sets of Small Sensity.

[BibT_eX]

[DOI]

Antoni Lozano

Math. Syst. Theory, 1991

Complexity Classes Defined by Counting Quantifiers.

[BibT_eX]

[DOI]

J. ACM, 1991

The MINSUMCUT Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1991

1990

Classes of Bounded Nondeterminism.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1990

Counting the Number of Solutions.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989

On Counting and Approximation.

[BibT_eX]

[DOI]

Acta Informatica, 1989

A Combinatorial Technique for Separating Counting Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Complexity Classes with Complete Problems Between P and NP-C.

[BibT_eX]

[DOI]

Carme Àlvarez

Proceedings of the Fundamentals of Computation Theory, 1989

1988

An oracle characterization of the counting hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Succinct Representations of Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1988

1987

On The Complexity of Computable Real Sequences.

[BibT_eX]

[DOI]