Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FUNCTIONAL ALGEBRAIC COMPUTATION:
Reports tagged with functional algebraic computation:
TR16-045 | 22nd March 2016
Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>




ISSN 1433-8092 | Imprint