Source author record

Vikraman Arvind

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable

The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. In the process we introduce the problem of isomorphism testing for higher-order hypergraphs and show that finding the automorphism group of order- $k$ hypergraphs with vertex color classes of size $b$ is fixed parameter tractable for any constant $k$ and $b$ as fixed parameter.

preprint2016arXiv

Identity Testing for +-Regular Noncommutative Arithmetic Circuits

An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can compute a polynomial of degree exponential in $s$ with a double-exponential number of nonzero monomials. In this paper, we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials): (1) We consider \emph{ $+$ -regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the $+$ -gates are layered, and in each $+$ -layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for $+$ -regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider $ΣΠ^*Σ$ noncommutative circuits: these are noncommutative circuits with layered $+$ -gates such that there are only two layers of $+$ -gates. These $+$ -layers are the output $+$ -gate and linear forms at the bottom layer; between the $+$ -layers the circuit could have any number of $\times$ gates. We given an efficient randomized \emph{black-box} identity testing problem for $ΣΠ^*Σ$ circuits. In particular, we show if $f\in F<Z>$ is a nonzero noncommutative polynomial computed by a $ΣΠ^*Σ$ circuit of size $s$ , then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(F)$ , where the field $F$ is a sufficiently large extension of $F$ depending on the degree of $f$ .

preprint2014arXiv

Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

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)})$ .

preprint2013arXiv

The Parameterized Complexity of some Permutation Group Problems

In this paper we study the parameterized complexity of two well-known permutation group problems which are NP-complete. 1. Given a permutation group G=<S>, subgroup of $S_n$ , and a parameter $k$ , find a permutation $π$ in G such that $|{i\in [n]\mid π(i)\ne i}|$ is at least $k$ . This generalizes the well-known NP-complete problem of finding a fixed-point free permutation in G. (this is the case when $k=n$ ). We show that this problem with parameter $k$ is fixed parameter tractable. In the process, we give a simple deterministic polynomial-time algorithm for finding a fixed point free element in a transitive permutation group, answering an open question of Cameron. 2. Next we consider the problem of computing a base for a permutation group G=<S>. A base for G is a subset B of $[n]$ such that the subgroup of G that fixes B pointwise is trivial. This problem is known to be NP-complete. We show that it is fixed parameter tractable for the case of cyclic permutation groups and for permutation groups of constant orbit size. For more general classes of permutation groups we do not know whether the problem is in FPT or is W[1]-hard.

preprint2010arXiv

The Remote Point Problem, Small Bias Space, and Expanding Generator Sets

Using $ε$ -bias spaces over $F_2$ , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace $F^n$ by $G^n$ for an arbitrary fixed group $G$ . When $G$ is Abelian, we give an $NC^2$ algorithm for RPP, again using $ε$ -bias spaces. For nonabelian $G$ , we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group $G^n$ . All our algorithms for the RPP achieve essentially the same parameters as [APY09].

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.