Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARITHMETIC FORMULAS:
Reports tagged with arithmetic formulas:
TR03-067 | 14th August 2003
Ran Raz

#### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

An arithmetic formula is multi-linear if the polynomial computed
by each of its sub-formulas is multi-linear. We prove that any
multi-linear arithmetic formula for the permanent or the
determinant of an $n \times n$ matrix is of size super-polynomial
in $n$.

more >>>

TR04-042 | 21st May 2004
Ran Raz

#### Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

An arithmetic circuit or formula is multilinear if the polynomial
computed at each of its wires is multilinear.
We give an explicit example for a polynomial $f(x_1,...,x_n)$,
with coefficients in $\{0,1\}$, such that over any field:
1) $f$ can be computed by a polynomial-size multilinear circuit
of depth $O(\log^2 ... more >>> TR07-031 | 26th March 2007 Yael Tauman Kalai, Ran Raz #### Interactive PCP An interactive-PCP (say, for the membership$x \in L$) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages$L$, there are interactive-PCPs that are significantly shorter than the known more >>> TR12-033 | 5th April 2012 Ankit Gupta, Neeraj Kayal, Youming Qiao #### Random Arithmetic Formulas can be Reconstructed Efficiently Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial$f$computed by an unknown/hidden arithmetic formula$\phi$reconstructs, on the average, an equivalent or smaller formula$\hat{\phi}$in time polynomial in the size of its output$\hat{\phi}$. Specifically, we consider arithmetic formulas wherein the ... more >>> TR13-091 | 17th June 2013 Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi #### A super-polynomial lower bound for regular arithmetic formulas. We consider arithmetic formulas consisting of alternating layers of addition$(+)$and multiplication$(\times)$gates such that the fanin of all the gates in any fixed layer is the same. Such a formula$\Phi$which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>> TR14-005 | 14th January 2014 Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan #### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas We show here a$2^{\Omega(\sqrt{d} \cdot \log N)}$size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree$d$on$N$variables (with$N = d^3$in our case) with$0, 1\$-coefficients such that
for any representation of ... more >>>

ISSN 1433-8092 | Imprint