Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARITHEMTIC CIRCUITS:
Reports tagged with Arithemtic Circuits:
TR16-171 | 3rd November 2016
Daniel Minahan, Ilya Volkovich

#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the
operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ... more >>>

TR16-187 | 21st November 2016
morris yau

#### Almost Cubic Bound for Depth Three Circuits in VP

Revisions: 3

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$
on $N = \Theta(n polylog(n))$
variables with degree $N$ being in VP such that every
$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.
We ... more >>>

TR17-028 | 17th February 2017
Mrinal Kumar

#### A quadratic lower bound for homogeneous algebraic branching programs

Revisions: 1

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>>

TR17-163 | 2nd November 2017
Michael Forbes, Amir Shpilka

#### A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits

In this paper we study the complexity of constructing a hitting set for $\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>>

TR19-034 | 5th March 2019
Pavel Hrubes

Revisions: 1

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>> TR19-171 | 27th November 2019 Oded Goldreich #### Improved bounds on the AN-complexity of multilinear functions Revisions: 5 We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number. This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ... more >>> TR21-081 | 14th June 2021 Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas #### Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits Revisions: 1 An Algebraic Circuit for a polynomial$P\in F[x_1,\ldots,x_N]$is a computational model for constructing the polynomial$P$using only additions and multiplications. It is a \emph{syntactic} model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to ... more >>> TR21-155 | 13th November 2021 Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha #### Learning generalized depth-three arithmetic circuits in the non-degenerate case Consider a homogeneous degree$d$polynomial$f = T_1 + \cdots + T_s$,$T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$where$g_i$'s are homogeneous$m$-variate degree$d$polynomials and$\ell_{i,j}$'s are linear polynomials in$n$variables. We design a (randomized) learning algorithm that given black-box access to$f\$, computes black-boxes for ... more >>>

ISSN 1433-8092 | Imprint