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

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

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

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

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

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 call \emph{intersecting} and \emph{quotienting} the ... more >>>

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 black-box function $f:R^m\rightarrow R$ (where we ... more >>>

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

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

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 polynomial in $\F\{x_1,\cdots,x_n\}$ of degree $d$ with ... more >>>

\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 \emph{constant} $k$ then there ... more >>>

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

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 $O(\log^6 n)$ random bits and Merlin ... more >>>

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

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

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 the Karp-Luby approximate counting ... more >>>

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 NP}}$. 2. The class IP[P$/$poly], consisting of ... more >>>

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 extraction to these complexity classes. ... more >>>

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

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