All reports by Author Thomas Thierauf:

__
TR20-098
| 4th July 2020
__

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf#### Impossibility of Derandomizing the Isolation Lemma for all Families

__
TR20-077
| 19th May 2020
__

Amit Sinhababu, Thomas Thierauf#### Factorization of Polynomials Given by Arithmetic Branching Programs

__
TR20-039
| 25th March 2020
__

Pranjal Dutta, Nitin Saxena, Thomas Thierauf#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

__
TR17-127
| 12th August 2017
__

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi#### Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

__
TR16-182
| 14th November 2016
__

Rohit Gurjar, Thomas Thierauf#### Linear Matroid Intersection is in quasi-NC

__
TR15-177
| 9th November 2015
__

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

__
TR15-021
| 5th February 2015
__

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf#### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

__
TR14-158
| 26th November 2014
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf#### Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

__
TR14-079
| 11th June 2014
__

Simon Straub, Thomas Thierauf, Fabian Wagner#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

__
TR13-112
| 12th August 2013
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf#### Exact Perfect Matching in Complete Graphs

__
TR13-019
| 31st January 2013
__

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf#### On Two-Level Poset Games

__
TR11-148
| 3rd November 2011
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf#### Planarizing Gadgets for Perfect Matching do not Exist

__
TR11-018
| 8th February 2011
__

Jochen Messner, Thomas Thierauf#### A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

__
TR10-050
| 25th March 2010
__

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner#### Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR09-029
| 3rd April 2009
__

Fabian Wagner, Thomas Thierauf#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1

__
TR07-068
| 24th July 2007
__

Thomas Thierauf, Fabian Wagner#### The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

__
TR06-129
| 6th October 2006
__

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf#### The polynomially bounded perfect matching problem is in NC^2

__
TR04-024
| 26th March 2004
__

Thomas Thierauf, Thanh Minh Hoang#### On Closure Properties of GapL

Revisions: 1
,
Comments: 1

__
TR01-028
| 16th March 2001
__

Thanh Minh Hoang, Thomas Thierauf#### The Complexity of the Minimal Polynomial

__
TR97-060
| 2nd December 1997
__

Manindra Agrawal, Thomas Thierauf#### The Satisfiability Problem for Probabilistic Ordered Branching Programs

__
TR96-040
| 21st May 1996
__

Thomas Thierauf#### The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1
,
Comments: 1

__
TR96-032
| 12th March 1996
__

Manindra Agrawal, Thomas Thierauf#### The Boolean Isomorphism Problem

__
TR96-001
| 10th January 1996
__

Manindra Agrawal, Richard Beigel, Thomas Thierauf#### Modulo Information from Nonadaptive Queries to NP

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

Amit Sinhababu, Thomas Thierauf

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 $\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was ... more >>>

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.

More precisely,

the property that we need is that every face of the polytope lies in an affine space defined ...
more >>>

Rohit Gurjar, Thomas Thierauf

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

A read once ABP is an arithmetic branching program with each variable occurring 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, i.e. ... more >>>

Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.

The obvious way to construct such a reduction is via a {\em planarizing ...
more >>>

Jochen Messner, Thomas Thierauf

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

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 [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.

We extend this result of [DLN$^+$09] further

to the ...
more >>>

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

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 ... more >>>

Fabian Wagner, Thomas Thierauf

We show that the reachability problem for directed graphs

that are either K_{3,3}-free or K_5-free

is in unambiguous log-space, UL \cap coUL.

This significantly extends the result of Bourke, Tewari, and Vinodchandran

that the reachability problem for directed planar graphs

is in UL \cap coUL.

Our algorithm decomposes ... more >>>

Thomas Thierauf, Fabian Wagner

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 ... more >>>

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The perfect matching problem is known to

be in P, in randomized NC, and it is hard for NL.

Whether the perfect matching problem is in NC is one of

the most prominent open questions in complexity

theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem

more >>>

Thomas Thierauf, Thanh Minh Hoang

We show necessary and sufficient conditions that

certain algebraic functions like the rank or the signature

of an integer matrix can be computed in GapL.

Thanh Minh Hoang, Thomas Thierauf

We investigate the computational complexity

of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial

is in AC^0(GapL), the AC^0-closure of the logspace

counting class GapL, which is contained in NC^2.

Our main result is that the problem is hard ...
more >>>

Manindra Agrawal, Thomas Thierauf

We show that the satisfiability problem for

bounded error probabilistic ordered branching programs is NP-complete.

If the error is very small however

(more precisely,

if the error is bounded by the reciprocal of the width of the branching program),

then we have a polynomial-time algorithm for the satisfiability problem.

more >>>

Thomas Thierauf

We investigate the computational complexity of the

isomorphism problem for one-time-only branching programs (BP1-Iso):

on input of two one-time-only branching programs B and B',

decide whether there exists a permutation of the variables of B'

such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

Manindra Agrawal, Thomas Thierauf

We investigate the computational complexity of the Boolean Isomorphism problem (BI):

on input of two Boolean formulas F and G decide whether there exists a permutation of

the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

Manindra Agrawal, Richard Beigel, Thomas Thierauf

The classes of languages accepted by nondeterministic polynomial-time

Turing machines (NP machines, in short) that have restricted access to

an NP oracle --- the machines can ask k queries to the NP oracle and

the answer they receive is the number of queries ...
more >>>