ECCC-Report TR13-174https://eccc.weizmann.ac.il/report/2013/174Comments and Revisions published for TR13-174en-usFri, 06 Dec 2013 12:59:31 +0200
Paper TR13-174
| Hitting-sets for low-distance multilinear depth-$3$ |
Arpita Korwar,
Manindra Agrawal,
Rohit Gurjar,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2013/174The 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.Fri, 06 Dec 2013 12:59:31 +0200https://eccc.weizmann.ac.il/report/2013/174