Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>

Nitin Saxena

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... 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 >>>

Shachar Lovett

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

Neeraj Kayal

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ ... more >>>

Pavel Hrubes

Koiran's real $\tau$-conjecture asserts that if a non-zero real polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij},$

where each $f_{ij}$ contains at most $k$ monomials, then the number of distinct real roots of $f$ is polynomial in $pqk$. We show that the conjecture implies quite a strong property of the ...
more >>>

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

We study the complexity of detecting monomials

with special properties in the sum-product

expansion of a polynomial represented by an arithmetic

circuit of size polynomial in the number of input

variables and using only multiplication and addition.

We focus on monomial properties expressed in terms

of the number of distinct ...
more >>>

Nitin Saxena

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>Stasys Jukna, Hannes Seiwert

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

Gaurav Sinha

In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>

Stasys Jukna, Hannes Seiwert, Igor Sergeev

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>