Information Technology Reference
In-Depth Information
5.9.3.2 Shifted Partials of the Nisan-Wigderson Polynomial
Very shortly after [ GKKS13 ]'s 2 ˇ( n ) lower bound, Kayal, Saha, and Saptharishi
[ KSS13 ] gave a stronger lower bound for a different polynomial. Their approach
was to engineer an explicit polynomial F for which the dimension of shifted partial
derivatives is easier to estimate. The main idea was that, if any k -th order partial
derivative of the engineered polynomial is a monomial, then once again estimating
dim ˃ = k
reduces to a monomial counting problem. If we could ensure
that no two monomials of F have a gcd of degree k or more, then we would imme-
diately get that all k -th order partial derivatives of F are just monomials (albeit
possibly zero). If we were to interpret the set of nonzero monomials of F as just
subsets over the variables, then the above constraint can be rephrased as a set system
with small pairwise intersection . Such systems are well studied and are known as
Nisan-Wigderson designs [ NW94 ]. With this in mind, [ KSS13 ] studied the following
polynomial family inspired by an explicit construction of a Nisan-Wigderson design.
)
(
F
Definition 53 ( Nisan-Wigderson Polynomial ) . Let n be a power of 2 and let
F n be
{
,...,
}
the finite field with n elements that are identified with the set
1
n
. For any
n , the polynomial NW k is a n 2 -variate polynomial of degree n defined as
0
k
follows:
NW k (
x 1 , 1 ,...,
x n , n ) =
x 1 , p ( 1 ) ...
x n , p ( n ) .
p
) ∗ F n [ t ]
deg
(
t
(
p
)<
k
It is easy to show that the above family of polynomials is in VNP . Further, since
any two distinct univariate polynomials of degree less than k intersects in less than
k places, we have the following observation.
Observation 54 Any two monomials of NW k intersect in less than k variables.
Hence, any k-th order partial derivative of NW k (
x
)
is a monomial (which could
possibly be zero).
Hence, the problem of lower bounding the shifted partials of NW k reduces to the
problem of counting distinct monomials of degree
k that are divisible by
one of these k -th order derivatives. [ KSS13 ] additionally used the observation that
two random k -th order partial derivatives of NW k are monomials that are far from
each other. Using this, they estimate the number of distinct shifts of these monomials
and showed that the dimension of shifted partial derivatives of NW k is very close
to the trivial upper bound as in Claim 47. We sketch the argument by Chillara and
Mukhopadhyay [ CM14 ]. Formally, for any twomultilinear monomials m 1 and m 2 ,let
the
+
d
(abusing notation
by identifying the multilinear monomials with the set of variables that divide it).
(
m 1 ,
m 2 )
denote min
{|
m 1 |−|
m 1
m 2 | ,
m 2 −|
m 1
m 2 |}
Lemma 55 [ CM14 ] Let m 1 ,...,
m s be monomials over N variables such that
(
m i ,
m j )
∅=
d for all i
j . Then the number of distinct monomials that may
Search WWH ::




Custom Search