Ran Raz

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

Ran Raz

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

Yael Tauman Kalai, Ran Raz

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

Ankit Gupta, Neeraj Kayal, Youming Qiao

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

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

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

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

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

Pranav Bisht, Nikhil Gupta, Ilya Volkovich

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

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

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