All reports by Author Gaurav Rattan:

__
TR15-032
| 21st February 2015
__

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky#### Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

__
TR15-004
| 4th January 2015
__

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan#### On the Complexity of Noncommutative Polynomial Factorization

__
TR14-111
| 15th August 2014
__

Vikraman Arvind, Gaurav Rattan#### Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

__
TR14-070
| 14th May 2014
__

Vikraman Arvind, Gaurav Rattan#### The Complexity of Geometric Graph Isomorphism

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

Color refinement is a classical technique used to show that two given graphs $G$ and $H$

are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

Vikraman Arvind, Gaurav Rattan

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous

best running time bound of $O^*(2^{O(k^2/\log

k)})$.

Vikraman Arvind, Gaurav Rattan

We study the complexity of Geometric Graph Isomorphism, in

$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,

B\subset \mathbb{Q}^k$ in

$k$-dimensional euclidean space the problem is to

decide if there is a bijection $\pi:A \rightarrow B$ such that for

...
more >>>