Information Technology Reference
In-Depth Information
[
GK
]
k
+
g)
≥
[
GK
]
k
)
+
[
GK
]
k
,A
(
,A
(
,A
(g)
Observation 21
(Sub-additivity)
f
f
.
Now fix a threshold
r
0
=
ʳ
n
for some constant
ʳ >
0 (to be chosen shortly), and
let
k
=
˕
n
for some
˕ >
0 (to be chosen shortly).We shall call a term
T
=
1
...
d
to
be of
low rank
if rank
r
0
, and
large rank
otherwise. By the above observation,
we need to upper bound themeasure
(
T
)
≥
[
GK
]
k
for each term
T
, for a suitable choice of
A
.
,A
Low rank terms
(
rank
(
T
)
≥
r
0
)
Suppose
T
=
1
...
d
with
{
1
,...,
r
}
being a maximal independent set of linear
polynomials (with
r
≥
r
0
). Then,
T
can be expressed as a linear combination of terms
from the set
⊞
]
⊠
. And since the matrix
M
k
(
e
1
1
e
r
r
...
:
e
i
≥
d
∞
i
∗[
r
f
)
depends
n
2
, we can use the relation that
x
q
only on evaluations in
F
=
x
in
F
to express the
as a linear combination of
⊞
]
⊠
.
n
2
e
1
1
e
r
r
: F
∩ F
...
:
<
∞
∗[
function
T
e
i
q
i
r
n
2
, we have that
Therefore, for any set
A
∧ F
[
GK
]
k
q
r
q
ʳ
n
;
A
(
T
)
≥
rank
(
M
k
(
f
))
≥
≥
.
High rank terms
(
rank
(
T
)>
r
0
)
Suppose
T
be
a maximal independent set. We want to use the fact that since
T
is a product of at
least
r
independent linear polynomials, most evaluations would be zero. We shall be
choosing our
=
1
...
d
whose rank is greater than
r
0
=
ʳ
n
, and let
{
1
,...,
r
}
to be the set where all
k
-th order partial derivatives evaluate to zero.
On applying the product rule of differentiation, any
k
-th order derivative of
T
can
be written as a sum of terms each of which is a product of at least
r
A
−
k
independent
n
2
linear polynomials. Let us count the
erroneous points
E
T
∧ F
that keep at least
r
−
k
of
{
1
,...,
r
}
nonzero, or in other words makes at most
k
of
{
1
,...,
r
}
zero.
⊣
r
i
⊤⊣
1
q
⊤
i
⊣
1
⊤
r
−
i
k
⊨
1
q
Pr
n
2
[
at most
k
of
1
,...,
r
evaluate to zero
]≥
−
∗
F
a
i
=
0
Hence, we can upper bound
|
E
T
|
as
⊣
r
i
⊤
k
⊨
i
q
n
2
r
−
−
r
|
E
T
| ≥
(
q
−
1
)
i
=
0
O
k
q
n
2
⊦
⊣
r
k
⊤⊣
1
⊤
r
−
k
1
q
=
·
−
if
r
>
qk
q
n
2
n
=
·
ʲ
for some 0
< ʲ <
1
.
E
=
T
of large rank
E
T
, we have that
M
k
(
n
2
A
= F
\
E
;
A)
By choosing
where
T
[
GK
]
k
is just the zero matrix and hence
,
A
(
T
)
=
0.
Putting it together, if
C
=
T
1
+···+
T
s
, then
