Information Technology Reference
In-Depth Information
ment preserves SM. So does the conversion from formulas to ABPs, [
Va l 7 9
]. But the
conversion from formulas to width-3 ABPs, [
BOC92
], does not. In fact, Rao [
Rao10
]
showed that even a significant generalisation of Ben-Or and Cleve's technique, using
polynomially many registers instead of just 3, cannot preserve syntactic multilinear-
ity. Of course, there may be other ways of going from SM-VF to SM-VBWBP, but
it could equally well be that the classes are distinct.
To get back perspective, in the SM world what we have seen so far is:
SM-VBWBP
SM-VF
SM-VBP
SM-VP
As mentioned earlier, Raz [
Raz06
] showed that the inclusion from SM-VF to SM-VP
is proper. Very recently, this was improved by Dvir et al. [
DMPY12
]. They showed
that in fact the inclusion SM-VF
SM-VBP is strict. Whether the first and the last
inclusion are strict is still open.
The proof of [
DMPY12
] is a clever adaptation of the original technique from
[
Raz06
]. Let us briefly examine this.
The central ingredient in Raz's proof is randomly partitioning the variables and
analysing the rank of the resulting partial derivatives matrix. Consider a polynomial
f
on 2
n
variables
X
={
x
1
,...,
x
2
n
}
, and consider a partition of
X
into equi-sized
2
n
matrix
M
Y
,
f
where rows and columns are indexed by
subsets of
Y
and
Z
(equivalently, multilinear monomials over
Y
and
Z
, respectively).
The entry
sets
Y
,
Z
. Consider a 2
n
×
m
z
in
f
. Intuitively, if
M
Y
,
f
has high rank, then
f
should be hard. But high rank with respect to what
partition? Raz showed that if multilinear
f
has small SM-formula size, then for
at least one partition
(
m
y
,
m
z
)
is the coefficient of the monomial
m
y
·
of
X
,
M
Y
,
f
will have low rank. (The existence of the
partition witnessing low rank is proved using the probabilistic method; choose a
partition at random, and analyse the probability that the resulting matrix has rank
exceeding some threshold.) He also constructed an explicit family
g
in SM-VSAC
1
and showed that for every partition
(
Y
,
Z
)
of
X
,
M
Y
,
Z
g
(
Y
,
Z
)
has high rank; hence
g
is not
in SM-VF.
The non-trivial adaptation done in [
DMPY12
] is to consider not all partitions,
but a fairly small set of what they call arc-partitions. They showed that if
f
is in
SM-VF, then for at least one arc-partition
of
X
,
M
Y
,
f
will have low rank.
They consider an explicit family
g
in SM-VBP and show that for every arc-partition
(
(
Y
,
Z
)
of
X
,
M
Y
,
Z
g
has high rank. Hence
g
is not in SM-VF. The low-rank proof is
again probabilistic, but it has a very appealing combinatorial flavour. So does the
very definition of an arc-partition.
Y
,
Z
)
4.5 More on Completeness
Assume that completeness is defined with respect to
p
-projections. If a family
(
f
n
)
(
f
n
)
is complete for a class, then understanding
better allows us to understand the
