Lecture 09 - Approximate Degree as LP

IIT Kanpur July 201
20 followers
May 31, 2024
[Music]
[Music]
let me give you more exercise and this
is going to be slightly more difficult
okay this is an exercise for you so
ready with pen and
paper okay this is the problem
of what we call approximate
okay what is approximate degree suppose
you are given a Boolean
function that means it takes an nbit
string and outputs of
it okay and now you want to write it as
a
polinomial what does it mean you want to
write
it
as a polinomial in X1 to xn such
that the value here matches at all the 2
the^ N possible inputs it's clear that
there are 2 the^ N possible inputs that
many strings my polinomial and you can
do it but that's kind of expensive in
the sense that you need a very high
degree polinomial so what people are
interested in is is it possible to
approximate this function
with a polinomial which has small
degree the question is clear what does
it mean you
want degree polinomial
P such that for all
X let's say the difference between PX
and F f
x is less than some constant and for r e
we will just say 1
by3 okay so this is first the notion
of approximate degree so let's take some
time to absorb
it once more we are given a function we
want to understand what is the best in
some sense polinomial
representation okay actually lot of lot
of it is known it is known that if you
want to have a polinomial representation
of it of this uh certain kind then there
is a unique polinomial so remember now
your X12 xn are real so this is a
polinomial where your coefficients are
coming from real in spite of that there
is a single polinomial which gives you
which agrees with this function on all
end
points this is one way in which you can
say that your polinomial represents a
function but this is very expensive in
the sense that you need a high degree so
what people mathematically are
interested in is is it possible that
there is a small degree
polinomial which is close to
F what does it mean close to s f for
every input it should not be more it
should not be away from FX by more than
1x3
distance clear and now we are interested
in finding
a smallest degree
polom
now uh one thing to notice is since your
input is only 0a 1 I never need a degree
higher than
1 my X1 square is equal to X1 I just
want to make sure that my
polinomial agrees at these points right
so I'm only interested in the value at
these points so there is no point having
X1 Square in my polinomial I can just
replace it by X1 and get the same thing
on all of these 2 The Power end
points right so that means my
polinomial if you think about
it
it will look like some coefficient of s
multiplied by the
monomial where
s right so there are at most 2 to the^ n
terms in my
polinomial right is this point clear to
you this is just to emphasize what we
are doing right and and just to tell you
this has problems in giving circuit
lower bounds uh secret sharing schemes
learning theory Quantum
Computing uh there are surveys about
this approximate degree and it has it
has applications in many many areas in
theoretical computer
science okay so now this is a problem
and one of the reason why this is
interesting is because there exist a
linear program for it
now can you make a linear program for
it what would you want to
minimize right this is going to be an
issue now you realize that degree
is
integer right so minimizing degree you
should kind of realize that oh that
doesn't look like a linear thing that is
going to be a problem okay okay so we
going to slightly change our problem and
we are going to
say given all degr polinomial of this
kind because you don't need higher
degree what is the best approximation
can I get and then I will say oh for 100
do I get 1x3 for 200 do I get 1x3 and as
soon as I get 1x3 I will say okay I'm
done right so in terms of polinomial is
not very expensive because I just have
to repeat my procedure end
times right so this is okay there's
number of variables there's still one
extra n so it's not very
expensive but now now this can you write
it as a linear program my claim is you
can so write a linear program what are
the variables what are the constraints
for this
problem and this is
interesting this is not that
straightforward and I would be happy to
explain any doubt here in terms of the
definition
of remember this is a
polinomial in R to the N that means the
coefficients are coming
from real numbers right but we only need
that it works fine on these Boolean
inputs I'm not entirely clear on what
we've just done Pol
whatever so I want to create a linear
program whose answer will give me what
is the best possible
approximation like uh uh so best
possible approximation is like the
maximum value of this for any degreed
polinomial so I'm not worried about how
big my linear program is but is there a
linear program which captures that
problem right so uh you can think of it
as what is the error for a polinomial p
the error
is this and I want to find out the best
degre polinomial
which okay so this goes in kind of two
steps generally when you define the
approximate degree you first fix a
constant you say that I want want to be
this close to my function 1x3 is an
arbitrary Choice it could be 1X two it
could be 1X 100 depending upon your
application okay and it turns out that
that doesn't affect the degree by much
but that's a separate proof now you have
fixed 1x3 you find you want to find the
smallest degree that's kind of hard
because you're optimizing degree which
kind of goes in the integer way I can't
put it in my constraints I can't put it
in my optimization problem so I flip the
problem instead of saying that I want
this to hold true I say let me look at
all degre polinomial and find out what
best approximation I can get and then I
will very D and I will stop as soon as I
get less than 1 by3
okay physically because of the duality
of the situation can do this uh yeah so
here your your Duality is English
Duality not the mathematical linear
program Duality
yes yeah you should be very careful now
especially speaking to me when you use
the word dual right
because so what should be the
variables
CI the CI what were the Cs you
mean okay and
approximation have you seen the program
before no okay approximation bound how
do you want
to uh how do you want to uh represent
it Alpha okay okay so now if these are
the variables what is your linear
program I know you you are close to it
but let's let's see if someone else can
answer you want to minimize
something
minimize bound means Alpha right yes so
you want to minimize
Alpha constraint is
is that what you're
saying
sorry yes yes we'll go to that but this
is true
for all
XS all n withd
strings is that is that
all no no no no we are not worried about
1x3 you just want to find the best
possible approximation here is that all
no you're missing something
here
no that you can put if you want but you
know uh linear program will take care of
it what
else
all the C have to be real so can also be
negative okay yes but I haven't put the
constraint that CI is greater than equal
to z0 or no no no it won't if if if it
just was outputting zero or one then the
degree would be very high the point is
now it can even answer 0.9 and it is
okay if FX is 1 then I'm fine with the
polinomial outputting
point9
but okay so how many variables are there
there D+ what is t d
d
no right so the point is the one thing
which is not clear here is that this is
only
a degree d
polinomial right so then remember even
though it looks like this x here is not
a variable
right I have written it like this but X
is not a variable the variables are the
coefficients and they will only go up to
the desize
subsets so that would be like n 0
plus right so I have these many
variables plus one for
Alpha is this a linear
program
not yet because
of absolute values but I'm sure all of
you can convert it into two constraints
both of which
are
linear okay and
uh I don't know about many other fields
but at least for Quantum Computing this
realization was very very important kind
of looking at this changing the problem
to the Dual nature and then writing out
this this thing this is the only way in
which we can bound approximate degree
for non-symmetric
functions this is the only Technique we
know and people have been working on it
for at least 20
years still not sorry the solution is
expon uh yeah so at this point you are
thinking of solution because you're
thinking I will feed this linear program
into a linear programming
solver but that is not what is expected
here what happens here is that you are
given a function you are given a
function like and or parity and you want
to find out whether its approximate
degree is root n or n or n the^ 2x3 so
it's never that you're going to feed
this into a linear programming solver
that will never give you the ASM totic
Bond it will only give it to you for one
particular n and doesn't that doesn't
give anything so just this linear
program you can write the Dual of it
equivalence and then you can make many
things with it so even though and there
is another very nice example where you
never actually solve the linear
program but the mathematical structure
the beauty of it which I have talked
about allows you to use this linear
program to give lot of information about
these things and we will see
it okay so generally our idea is oh
create a linear program put it to the
solver that's not it
okay like like a general stupid course
in linear program will just tell you
Simplex method take the linear program
put into Simplex method but there is
much more to it and that's why we have
to take the comprehensive view of what
linear program is and we will talk about
it okay did I answer your question so
yeah I'm not worried that I can't solve
it by putting it in the linear
programming solver I'm just interested
that it is a linear program
okay
[Music]
[Music]
[Music]
