Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR23-109 | 21st July 2023
Pranav Bisht, Nikhil Gupta, Ilya Volkovich

Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>

TR24-041 | 1st March 2024
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Launching Identity Testing into (Bounded) Space

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).
First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ... more >>>

ISSN 1433-8092 | Imprint