In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-$4$ multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-$4$ circuits with a plus gate at the top (also known as $\Spsp$ circuits) and has a running time of $\exp(\poly(\log(n),\log(s),k))$ where $n$ is ... 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 >>>

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