Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARITHMETIC CIRCUIT COMPLEXITY:
Reports tagged with Arithmetic Circuit Complexity:
TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the ... more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

Arithmetic Complexity, Kleene Closure, and Formal Power Series

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

TR18-068 | 8th April 2018
Mrinal Kumar

On top fan-in vs formal degree for depth-3 arithmetic circuits

Revisions: 1

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>

TR18-095 | 11th May 2018
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Hardness Amplification for Non-Commutative Arithmetic Circuits

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>

TR18-180 | 3rd November 2018
Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

Lower bounds for arithmetic circuits via the Hankel matrix

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>

TR19-037 | 5th March 2019
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Closure of VP under taking factors: a short and simple proof

Revisions: 1

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

TR20-045 | 15th April 2020
Ankit Garg, Neeraj Kayal, Chandan Saha

Learning sums of powers of low-degree polynomials in the non-degenerate case

Revisions: 1

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as
$$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$
where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = ... more >>> TR20-129 | 5th September 2020 Mrinal Kumar, Ben Lee Volk A Lower Bound on Determinantal Complexity The determinantal complexity of a polynomial$P \in \mathbb{F}[x_1, \ldots, x_n]$over a field$\mathbb{F}$is the dimension of the smallest matrix$M$whose entries are affine functions in$\mathbb{F}[x_1, \ldots, x_n]$such that$P = Det(M)$. We prove that the determinantal complexity of the polynomial$\sum_{i = 1}^n x_i^n$... more >>> TR21-094 | 6th July 2021 Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas New Non-FPT Lower Bounds for Some Arithmetic Formulas An Algebraic Formula for a polynomial$P\in F[x_1,\ldots,x_N]$is an algebraic expression for$P(x_1,\ldots,x_N)$using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class$\mathrm{NC}^1.\$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

ISSN 1433-8092 | Imprint