Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARITHMETIC CIRCUIT:
Reports tagged with arithmetic circuit:
TR97-016 | 29th April 1997
Manindra Agrawal, Eric Allender, Samir Datta

#### On TC^0, AC^0, and Arithmetic Circuits

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

TR07-124 | 23rd November 2007
Nitin Saxena

#### Diagonal Circuit Identity Testing and Lower Bounds

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

TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

#### Arithmetic Circuit Size, Identity Testing, and Finite Automata

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

TR11-094 | 20th June 2011
Shachar Lovett

#### Computing polynomials with few multiplications

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

TR12-081 | 26th June 2012
Neeraj Kayal

#### An exponential lower bound for the sum of powers of bounded degree polynomials

Revisions: 1

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

TR12-121 | 25th September 2012
Pavel Hrubes

#### A note on the real $\tau$-conjecture and the distribution of roots

Revisions: 2

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

TR13-139 | 7th October 2013
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

#### Detecting Monomials with $k$ Distinct Variables

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

TR13-186 | 27th December 2013
Nitin Saxena

#### Progress on Polynomial Identity Testing - II

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

TR18-049 | 14th March 2018
Stasys Jukna, Hannes Seiwert

#### Greedy can also beat pure dynamic programming

Revisions: 1

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

TR20-125 | 17th August 2020
Gaurav Sinha

#### Efficient reconstruction of depth three circuits with top fan-in two

Revisions: 1

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

TR20-178 | 30th November 2020
Stasys Jukna, Hannes Seiwert, Igor Sergeev

#### Reciprocal Inputs in Arithmetic and Tropical Circuits

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

TR21-045 | 22nd March 2021
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

#### Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

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

ISSN 1433-8092 | Imprint