Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-174 | 6th December 2013 11:59

Hitting-sets for low-distance multilinear depth-$3$


Authors: Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Publication: 6th December 2013 12:59
Downloads: 2443


The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of distance for multilinear depth-$3$ circuits (say, in $n$ variables and $k$ product gates) that measures how far are the partitions from a mere refinement. The $1$-distance strictly subsumes the set-multilinear model, while $n$-distance captures general multilinear depth-$3$. We design a hitting-set in time poly($n^{delta \log k}$) for $delta$-distance. Further, we give an extension of our result to models where the distance is large (close to $n$) but it is small when restricted to certain variables. This implies the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-$3$ circuits.

We also explore a new model of read-once algebraic branching programs (ROABP) where the factor-matrices are invertible (called invertible-factor ROABP). We design a hitting-set in time poly($\text{size}^{w^2}$) for width-$w$ invertible-factor ROABP. Further, we could do without the invertibility restriction when $w=2$. Previously, the best result for width-$2$ ROABP was quasi-polynomial time (Forbes-Saptharishi-Shpilka, arXiv 2013).

The common thread in all these results is the phenomenon of low-support 'rank concentration'. We exploit the structure of these models to prove rank-concentration after a 'small shift' in the variables. Our proof techniques are stronger than the results of Agrawal-Saha-Saxena (STOC 2013) and Forbes-Saptharishi-Shpilka (arXiv 2013); giving us quasi-polynomial-time hitting-sets for models where no subexponential whitebox algorithms were known before.

ISSN 1433-8092 | Imprint