Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with arithmetic complexity:
TR01-095 | 12th November 2001
Hubie Chen

Arithmetic Versions of Constant Depth Circuit Complexity Classes

The boolean circuit complexity classes
AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied
intensely. Other than NC^1, they are defined by constant-depth
circuits of polynomial size and unbounded fan-in over some set of
allowed gates. One reason for interest in these classes is that they
contain the ... more >>>

TR11-133 | 4th October 2011
Maurice Jansen, Rahul Santhanam

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

TR16-002 | 18th January 2016
Ryan Williams

Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,
$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ... more >>>

TR16-094 | 6th June 2016
Guillaume Lagarde, Guillaume Malod

Non-commutative computations: lower bounds and polynomial identity testing

Comments: 1

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize algebraic branching programs (ABP). This model is called unambiguous because it captures the
polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-
We ... more >>>

TR17-077 | 30th April 2017
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

ISSN 1433-8092 | Imprint