Document

**Published in:** LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. Its minimum is the support-sum S(f) of f.
For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of, a full-support univariate polynomial, f of degree d is S(f) ≥ d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) ≥ d^{0.5+ε(d)}, for a sub-constant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Θ(d).
We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.

Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.ITCS.2021.23, author = {Dutta, Pranjal and Saxena, Nitin and Thierauf, Thomas}, title = {{A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {23:1--23:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.23}, URN = {urn:nbn:de:0030-drops-135629}, doi = {10.4230/LIPIcs.ITCS.2021.23}, annote = {Keywords: VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound} }

Document

**Published in:** LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).

Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33, author = {Sinhababu, Amit and Thierauf, Thomas}, title = {{Factorization of Polynomials Given By Arithmetic Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {33:1--33:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.33}, URN = {urn:nbn:de:0030-drops-125854}, doi = {10.4230/LIPIcs.CCC.2020.33}, annote = {Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

We present a geometric approach towards derandomizing the {Isolation Lemma} by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of weights, where each weight is an integer and quasi-polynomially bounded, that can isolate a vertex in any 0/1 polytope for which each face lies in an affine space defined by a totally unimodular matrix. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the Isolation Lemma for {bipartite perfect matching} and {matroid intersection}. We prove our result by associating a {lattice} to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids.

Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.ICALP.2018.74, author = {Gurjar, Rohit and Thierauf, Thomas and Vishnoi, Nisheeth K.}, title = {{Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {74:1--74:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.74}, URN = {urn:nbn:de:0030-drops-90782}, doi = {10.4230/LIPIcs.ICALP.2018.74}, annote = {Keywords: Derandomization, Isolation Lemma, Total unimodularity, Near-shortest vectors in Lattices, Regular matroids} }

Document

**Published in:** Dagstuhl Reports, Volume 6, Issue 10 (2017)

Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures.
It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples.
The algebraic theme continues in some of the most exciting recent progress in
computational complexity. There have been significant recent advances in
algebraic circuit lower bounds, and the so-called chasm at depth 4
suggests that the restricted models now being considered are not so far from
ones that would lead to a general result. There have been similar successes
concerning the related problems of polynomial identity testing and circuit
reconstruction in the algebraic model (and these are tied to central
questions regarding the power of randomness in computation).
Another surprising connection is that the algebraic techniques invented to show lower bounds now prove useful to develop efficient algorithms. For example,
Williams showed how to use the polynomial method to obtain faster all-pair-shortest-path algorithms. This emphases once again the central role of algebra in computer science.
The seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar can play an important role in educating a diverse community about the latest new techniques, spurring further progress.

Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). In Dagstuhl Reports, Volume 6, Issue 10, pp. 13-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{kabanets_et_al:DagRep.6.10.13, author = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)}}, pages = {13--32}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {10}, editor = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.10.13}, URN = {urn:nbn:de:0030-drops-69504}, doi = {10.4230/DagRep.6.10.13}, annote = {Keywords: Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits} }

Document

**Published in:** LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs.
ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time.
Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.CCC.2015.323, author = {Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin and Thierauf, Thomas}, title = {{Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {323--346}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323}, URN = {urn:nbn:de:0030-drops-50647}, doi = {10.4230/LIPIcs.CCC.2015.323}, annote = {Keywords: PIT, Hitting-set, Sum of ROABPs, Evaluation Dimension, Rank Concentration} }

Document

**Published in:** Dagstuhl Reports, Volume 4, Issue 9 (2015)

At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples.
The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called "chasm at depth 4" suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model, and these are tied to central questions regarding the power of randomness in computation. Representation theory has emerged as an important tool in three separate lines of work: the "Geometric Complexity Theory" approach to P vs. NP and circuit lower bounds, the effort to resolve the complexity of matrix multiplication, and a framework for constructing locally testable codes. Coding theory has seen several algebraic innovations in recent years, including multiplicity codes, and new lower bounds.
This seminar brought together researchers who are using a diverse array of algebraic methods in a variety of settings. It plays an important role in educating a diverse community about the latest new techniques, spurring further progress.

Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans. Algebra in Computational Complexity (Dagstuhl Seminar 14391). In Dagstuhl Reports, Volume 4, Issue 9, pp. 85-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.4.9.85, author = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, title = {{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}}, pages = {85--105}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.9.85}, URN = {urn:nbn:de:0030-drops-48851}, doi = {10.4230/DagRep.4.9.85}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 10 (2013)

At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove
things about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on
algebraic proof techniques. The PCP characterization of NP and the
Agrawal-Kayal-Saxena polynomial-time primality test are two prominent examples.
Recently, there have been some works going in the opposite direction, giving alternative combinatorial proofs for results that were originally proved
algebraically. These alternative proofs can yield important improvements because they are closer to the underlying problems and avoid the losses in passing to the algebraic setting. A prominent example is Dinur's proof of the PCP Theorem via gap amplification which yielded short PCPs with only a polylogarithmic length blowup (which had been the focus of significant research effort up to that point). We see here (and in a number of recent works) an exciting interplay between algebraic and combinatorial techniques.
This seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and combinatorial methods in a variety of settings.

Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). In Dagstuhl Reports, Volume 2, Issue 10, pp. 60-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.2.10.60, author = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, title = {{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}}, pages = {60--78}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {10}, editor = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.10.60}, URN = {urn:nbn:de:0030-drops-39034}, doi = {10.4230/DagRep.2.10.60}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

From 11.10. to 16.10.2009, the Dagstuhl Seminar 09421 ``Algebraic Methods in Computational Complexity '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.1, author = {Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher}, title = {{09421 Abstracts Collection – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.1}, URN = {urn:nbn:de:0030-drops-24181}, doi = {10.4230/DagSemProc.09421.1}, annote = {Keywords: Computational Complexity, Algebra} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

The seminar brought together more than 50 researchers covering
a wide spectrum of complexity theory. The focus on algebraic
methods showed once again the great importance of algebraic
techniques for theoretical computer science. We had almost 30
talks, most of them about 40 minutes leaving ample room for
discussions. We also had a much appreciated open problem
session.
The talks ranged over a
broad assortment of subjects with the underlying theme of using
algebraic techniques. It was very fruitful and has hopefully
initiated new directions in research. Several participants
specifically mentioned that they appreciated the particular
focus on a common class of techniques (rather than end
results) as a unifying theme of the workshop. We look forward
to our next meeting!

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.2, author = {Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher}, title = {{09421 Executive Summary – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--4}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.2}, URN = {urn:nbn:de:0030-drops-24100}, doi = {10.4230/DagSemProc.09421.2}, annote = {Keywords: Computational Complexity, Algebra} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Graph Isomorphism is the prime example of a computational problem with a wide
difference between the best known lower and upper bounds on its complexity. There
is a significant gap between extant lower and upper bounds for planar graphs as well.
We bridge the gap for this natural and important special case by presenting an upper
bound that matches the known log-space hardness [JKMT03]. In fact, we show the
formally stronger result that planar graph canonization is in log-space. This improves the
previously known upper bound of AC1 [MR91].
Our algorithm first constructs the biconnected component tree of a connected planar
graph and then refines each biconnected component into a triconnected component
tree. The next step is to log-space reduce the biconnected planar graph isomorphism and
canonization problems to those for 3-connected planar graphs, which are known to be in
log-space by [DLN08]. This is achieved by using the above decomposition, and by making
significant modifications to Lindell’s algorithm for tree canonization, along with changes
in the space complexity analysis.
The reduction from the connected case to the biconnected case requires further new
ideas including a non-trivial case analysis and a group theoretic lemma to bound the
number of automorphisms of a colored 3-connected planar graph.

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:DagSemProc.09421.6, author = {Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian}, title = {{Planar Graph Isomorphism is in Log-Space}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--32}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.6}, URN = {urn:nbn:de:0030-drops-24169}, doi = {10.4230/DagSemProc.09421.6}, annote = {Keywords: Planar Graphs, Graph Isomorphism, Logspace} }

Document

**Published in:** LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Graph isomorphism is an important and widely studied computational problem with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space.
We extend this result %of \cite{DLNTW09}
further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as
a minor, and give a log-space algorithm.
Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected
components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected
component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09}
can then be used to decide the isomorphism problem.
For $K_5$ minor-free graphs, we consider $3$-connected components.
These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices
or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}.
We give an algorithm to get a unique
decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components,
and construct trees, accordingly.
Since the algorithm of \cite{DLNTW09} does
not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2009.2314, author = {Datta, Samir and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian}, title = {{Graph Isomorphism for K\underline\{3,3\}-free and K\underline5-free graphs is in Log-space}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {145--156}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2314}, URN = {urn:nbn:de:0030-drops-23144}, doi = {10.4230/LIPIcs.FSTTCS.2009.2314}, annote = {Keywords: Graph isomorphism, K\underline\{3,3\}-free graphs, K\underline5-free graphs, log-space} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

The isomorphism problem for planar graphs is known to be
efficiently solvable. For planar 3-connected graphs, the
isomorphism problem can be solved by efficient parallel algorithms,
it is in the class $AC^1$.
In this paper we improve the upper bound for planar 3-connected
graphs to unambiguous logspace, in fact to $UL cap coUL$. As a
consequence of our method we get that the isomorphism problem for
oriented graphs is in $NL$. We also show that the problems are
hard for $L$.

Thomas Thierauf and Fabian Wagner. The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 633-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{thierauf_et_al:LIPIcs.STACS.2008.1327, author = {Thierauf, Thomas and Wagner, Fabian}, title = {{The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {633--644}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1327}, URN = {urn:nbn:de:0030-drops-13273}, doi = {10.4230/LIPIcs.STACS.2008.1327}, annote = {Keywords: } }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.1, author = {Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas}, title = {{07411 Abstracts Collection – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--13}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7411}, editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.1}, URN = {urn:nbn:de:0030-drops-13072}, doi = {10.4230/DagSemProc.07411.1}, annote = {Keywords: Computational complexity, algebra, quantum computing, (de-) randomization} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

The seminar brought together almost 50 researchers covering a wide
spectrum of complexity theory. The focus on algebraic methods showed
once again the great importance of algebraic techniques for
theoretical computer science. We had almost 30 talks of length
between 15 and 45 minutes. This left enough room for discussions. We
had an open problem session that was very much appreciated.

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.2, author = {Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas}, title = {{07411 Executive Summary – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7411}, editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.2}, URN = {urn:nbn:de:0030-drops-13061}, doi = {10.4230/DagSemProc.07411.2}, annote = {Keywords: Computational complexity, algebra, quantum computing, (de-) randomization} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

From 10.10.04 to 15.10.04, the Dagstuhl Seminar 04421
``Algebraic Methods in Computational Complexity''
was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 04421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:DagSemProc.04421.1, author = {Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas}, title = {{04421 Abstracts Collection – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {4421}, editor = {Harry Buhrman and Lance Fortnow and Thomas Thierauf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.1}, URN = {urn:nbn:de:0030-drops-1162}, doi = {10.4230/DagSemProc.04421.1}, annote = {Keywords: Computational complexity , algebraic methods , quantum computations , lower bounds} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421). Dagstuhl Seminar Report 357, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{buhrman_et_al:DagSemRep.357, author = {Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas}, title = {{Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421)}}, pages = {1--16}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {357}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.357}, URN = {urn:nbn:de:0030-drops-152377}, doi = {10.4230/DagSemRep.357}, }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail