Information Technology Reference
In-Depth Information
of sparsity at most s , was worked out in [ BMS13 ]. The proof follows exactly the
above strategy. The time complexity is polynomial in size
C )
C ))
r ,
(
(
·
(
and
s
deg
where the exponential dependence comes from the sparsity estimate of
J x (
f
)
(and
C )
of course the final brute-force hitting-set for the r -variate ϕ(
).
Agrawal et al. [ ASSS12 ] extended the recipe to depth-4 circuits ( 7.1 ) where the
number of f i , j 's where any variable appears is bounded by r
5 This model is called
occur-r depth-4; it generalizes the well-studied multilinear read- r depth-4. Interest-
ingly, slightly modified techniques also provided exponential lower bounds against
these special models. This required proving some combinatorial properties of the
derivatives of immanant (e.g. permanent, determinant).
The faithful maps recipe has been able to unify all the assorted poly-time hitting-
sets known. However, one drawback is that it needs the characteristic to be zero/large.
Baby steps in resolving that issue have been taken by [ MSS12 ].
.
7.4 Rank Concentration, Shift, Hitting-Sets
The hitting-sets that we saw till nowwere for models where some parameter was kept
bounded. But we could also study models with a 'structural' restriction, e.g. mul-
tilinearity. This route has also been successful and enlightening. We call a depth-3
circuit C
= i T i multilinear if the linear factors in T i involve disjoint variables.
Hence, each product gate T i induces a partition
P i on the variables (or indices)
[
n
]
.
Moreover, we call C set-multilinear if these partitions are the same across all T i 's.
There is a large body of work on the set-multilinear model [ RS05 , AMS10 , FS12 ,
FS13b , ASS13 , FS13a , FSS13 , AGKS13 ]. The motivation for this model is, on the
one hand, the algebraic concept of tensors , and, on the other hand, the interest in read-
once boolean branching programs [ Nis92 , IMZ12 , Vad12 ]. Interestingly, [ FSS13 ]
has shown (extending the ideas of [ ASS13 ]) that the current situation in the arithmetic
world is exponentially better than that in the boolean one!
Here we will exhibit the key ideas of [ ASS13 ] and [ AGKS13 ]ontwo toy cases
that are already quite instructive; this saves us from the gory technical machinery
that drives the more general cases.
7.4.1 Multilinear ROABP
Agrawal et al. [ ASS13 ] gave the first quasi-poly-time hitting-set for set-multilinear
depth-3 (and extensions to constant-depth, non-multilinear versions). This was gen-
eralized by [ FSS13 ]to any depth; in fact, they dealt directly with the multilinear
ROABP D
i
, where L i 's are linear polynomials in disjoint
variables. Both the papers proved 'low-support rank concentration' in their models.
=
L i over M w ( F )
5 Note that this does not mean that trdeg
(
f i , j
|
i
,
j
)
is bounded.
Search WWH ::




Custom Search