All reports by Author Vikraman Arvind:

__
TR19-063
| 28th April 2019
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Efficient Black-Box Identity Testing for Free Group Algebra

__
TR18-111
| 4th June 2018
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

__
TR17-074
| 29th April 2017
__

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S#### Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

__
TR16-193
| 22nd November 2016
__

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S#### Identity Testing for +-Regular Noncommutative Arithmetic Circuits

__
TR16-157
| 13th October 2016
__

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran#### Parameterized Complexity of Small Weight Automorphisms

__
TR16-089
| 2nd June 2016
__

Vikraman Arvind, Partha Mukhopadhyay, Raja S#### Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

__
TR15-176
| 6th November 2015
__

Vikraman Arvind, Raja S#### Some Lower Bound Results for Set-Multilinear Arithmetic Computations

Revisions: 1

__
TR15-124
| 3rd August 2015
__

Vikraman Arvind, Pushkar Joglekar, Raja S#### Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

__
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-096
| 29th July 2014
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran#### Solving Linear Equations Parameterized by Hamming Weight

__
TR14-070
| 14th May 2014
__

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

__
TR14-028
| 27th February 2014
__

Vikraman Arvind, S Raja#### The Complexity of Two Register and Skew Arithmetic Computation

__
TR12-078
| 14th June 2012
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev#### Approximate Graph Isomorphism

__
TR11-140
| 31st October 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev#### Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

__
TR11-137
| 14th October 2011
__

Vikraman Arvind, Yadu Vasudev#### Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits

__
TR11-081
| 15th May 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar#### Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

__
TR10-069
| 17th April 2010
__

Eric Allender, Vikraman Arvind, Fengming Wang#### Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1
,
Comments: 1

__
TR09-122
| 23rd November 2009
__

Vikraman Arvind, Srikanth Srinivasan#### Circuit Lower Bounds, Help Functions, and the Remote Point Problem

__
TR09-105
| 27th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

__
TR09-103
| 26th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### On the Hardness of the Noncommutative Determinant

__
TR09-093
| 8th October 2009
__

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

__
TR09-073
| 6th September 2009
__

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan#### On Lower Bounds for Constant Width Arithmetic Circuits

__
TR09-026
| 17th February 2009
__

Vikraman Arvind, Pushkar Joglekar#### Arithmetic Circuit Size, Identity Testing, and Finite Automata

__
TR08-086
| 9th July 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Quantum Query Complexity of Multilinear Identity Testing

__
TR08-052
| 29th April 2008
__

Vikraman Arvind, T.C. Vijayaraghavan#### The Orbit problem is in the GapL Hierarchy

Revisions: 1

__
TR08-049
| 10th April 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

__
TR08-025
| 3rd January 2008
__

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan#### New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

__
TR07-095
| 13th July 2007
__

Vikraman Arvind, Partha Mukhopadhyay#### The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

__
TR04-121
| 7th December 2004
__

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan#### Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

__
TR04-008
| 27th November 2003
__

Vikraman Arvind, Jacobo Toran#### Solvable Group Isomorphism is (almost) in NP\cap coNP

__
TR03-064
| 23rd June 2003
__

Vikraman Arvind, Piyush Kurur#### Upper Bounds on the Complexity of some Galois Theory Problems

__
TR02-037
| 21st May 2002
__

Vikraman Arvind, Piyush Kurur#### Graph Isomorphism is in SPP

__
TR02-031
| 30th April 2002
__

Vikraman Arvind, Venkatesh Raman#### Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

__
TR99-033
| 19th August 1999
__

Vikraman Arvind, J. Köbler#### Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

__
TR99-008
| 19th March 1999
__

Eric Allender, Vikraman Arvind, Meena Mahajan#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1
,
Comments: 1

__
TR98-078
| 1st December 1998
__

Vikraman Arvind, K.V. Subrahmanyam, Vinodchandran Variyam#### The Query Complexity of Program Checking by Constant-Depth Circuits

__
TR98-027
| 15th April 1998
__

Vikraman Arvind, Jacobo Toran#### Sparse sets, approximable sets, and parallel queries to NP

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Hrubeš and Wigderson [HW14] initiated the study of

noncommutative arithmetic circuits with division computing a

noncommutative rational function in the free skew field, and

raised the question of rational identity testing. It is now known

that the problem can be solved in deterministic polynomial time in

more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,

computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or

$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a

deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing

algorithm to check whether $f \equiv 0$ or ...
more >>>

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

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

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Raja S

In this paper we show that polynomial identity testing for

noncommutative circuits of size $s$, computing a polynomial in

$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm

with running time polynomial in $s$ and $n$. This answers a question

that has been open for over ten years.

The ... more >>>

Vikraman Arvind, Raja S

In this paper, we study the structure of set-multilinear arithmetic

circuits and set-multilinear branching programs with the aim of

showing lower bound results. We define some natural restrictions of

these models for which we are able to show lower bound results. Some

of our results extend existing lower bounds, while ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Raja S

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and

$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some

striking connections to classical formal language theory. Our main

results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>

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, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:

1. Does $Ax=b$ have a solution of weight at most $t$?

2. Does $Ax=b$ have a solution of weight exactly $t$?

3. Does $Ax=b$ have a ...
more >>>

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

Vikraman Arvind, S Raja

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound

for a model of 2-register straight-line programs (SLPs) which is a universal model

of computation (unlike width-2 algebraic branching programs that ...
more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

Vikraman Arvind, Yadu Vasudev

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

Eric Allender, Vikraman Arvind, Fengming Wang

A recurring theme in the literature on derandomization is that probabilistic

algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is

needed for derandomization, existing lower bounds seem rather pathetic ...
more >>>

Vikraman Arvind, Srikanth Srinivasan

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

Vikraman Arvind, Srikanth Srinivasan

Using $\epsilon$-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 ... more >>>

Vikraman Arvind, Srikanth Srinivasan

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.

1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ...
more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay

Motivated by the quantum algorithm in \cite{MN05} for testing

commutativity of black-box groups, we study the following problem:

Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where

$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a

multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as

a ...
more >>>

Vikraman Arvind, T.C. Vijayaraghavan

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in

\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a

non-negative integer $i$ such that $A^i\x=\y$. This problem was

shown to be in deterministic polynomial time by Kannan and Lipton in

\cite{KL1986}. In this paper we place ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay

We give a randomized polynomial-time identity test for

noncommutative circuits of polynomial degree based on the isolation

lemma. Using this result, we show that derandomizing the isolation

lemma implies noncommutative circuit size lower bounds. More

precisely, we consider two restricted versions of the isolation

lemma and show that derandomizing each ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the \emph{noncommutative}

polynomial identity testing problem (first introduced and studied by

Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,

given as input a noncommutative

circuit $C(x_1,\cdots,x_n)$ computing a ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay

\begin{abstract}

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$

are monomials and a polynomial $f$ as an arithmetic circuit the

\emph{Ideal Membership Problem } is to test if $f\in I$. We study

this problem and show the following results.

\begin{itemize}

\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a

more >>>

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

In this paper we study the complexity of Bounded Color

Multiplicity Graph Isomorphism (BCGI): the input is a pair of

vertex-colored graphs such that the number of vertices of a given

color in an input graph is bounded by $b$. We show that BCGI is in the

#L hierarchy ...
more >>>

Vikraman Arvind, Jacobo Toran

The Group Isomorphism problem consists in deciding whether two input

groups $G_1$ and $G_2$ given by their multiplication tables are

isomorphic. We first give a 2-round Arthur-Merlin protocol for the

Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$

of size $n$, Arthur uses ...
more >>>

Vikraman Arvind, Piyush Kurur

Given a polynomial f(X) with rational coefficients as input

we study the problem of (a) finding the order of the Galois group of

f(X), and (b) determining the Galois group of f(X) by finding a small

generator set. Assuming the generalized Riemann hypothesis, we prove

the following complexity bounds:

1. ... more >>>

Vikraman Arvind, Piyush Kurur

We show that Graph Isomorphism is in the complexity class

SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for

each $k\geq 2$). We derive this result as a corollary of a more

general result: we show that a {\em generic problem} $\FINDGROUP$ has

an $\FP^{\SPP}$ ...
more >>>

Vikraman Arvind, Venkatesh Raman

We give a randomized approximation algorithm taking

$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a

$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph

$G$ with approximation ratio $1/k^{O(k)}$ and error probability

inverse exponential in $n$. This algorithm is based on ...
more >>>

Vikraman Arvind, J. Köbler

We show the following new lowness results for the probabilistic

class ZPP$^{\mbox{\rm NP}}$.

1. The class AM$\cap$coAM is low for ZPP$^{\mbox{\rm NP}}$.

As a consequence it follows that Graph Isomorphism and several

group-theoretic problems known to be in AM$\cap$coAM are low for

ZPP$^{\mbox{\rm ...
more >>>

Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Vikraman Arvind, K.V. Subrahmanyam, Vinodchandran Variyam

In this paper we study program checking (in the

sense of Blum and Kannan) using constant-depth circuits as

checkers. Our focus is on the number of queries made by the

checker to the program being checked and we term this as the

query complexity of the checker for the given ...
more >>>

Vikraman Arvind, Jacobo Toran

We relate the existence of disjunctive hard sets for NP to

other well studied hypotheses in complexity theory showing

that if an NP-complete set or a coNP-complete set is

polynomial-time disjunctively reducible

to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using

a similar argument we obtain also that ...
more >>>