YT YouTube2Text

YouTube2Text → Transcripts → ETH False II: completing the proof

ETH False II: completing the proof — Transcript

by Ryan O'Donnell · 11,374 words · 2,111 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01Okay, we're back.
0:02Hope you had a nice democracy day
0:05and are ready for some more
0:07ETH false. So, we're going to dive right
0:10into it. Hopefully, we'll be able to
0:12complete the proof.
0:13I'm not sure how much time we'll get,
0:14but we'll do our best.
0:17So, where were we? We were proving that
0:19uh
0:20sharp 3-SAT for sparse uh sharp 3-SAT
0:22instances can be solved in
0:24sub-exponential time, basically 2 to the
0:25end over root log n up to some polylogs
0:27polylog logs.
0:29And we immediately reduced this to
0:31computing permanents in the same amount
0:33of time. So, the task we want to solve
0:35is given an n by n matrix A where each
0:37row and column has uh constantly many
0:40non-zeros,
0:41uh we want to compute its permanent in
0:43this amount of time.
0:45And this was our plan. Hopefully, you
0:47remember some aspects of it.
0:50Um
0:50so, we want to construct a matrix
0:53polynomial,
0:54uh like a polynomial in matrices with a
0:57one parameter t
0:58>> [snorts]
0:59>> uh such that for this special value L,
1:02which is about log n,
1:04uh we have all these properties. So,
1:05first of all, the degree of this matrix
1:07polynomial should be uh a number d which
1:09is right around square root L. And
1:11perhaps you remember the fact that this
1:13is square root L and rather than L was
1:15like the ultimate source of this root
1:17log n savings.
1:19Um and then if we define p(t), which is
1:21just a univariate polynomial in numbers
1:23to be the permanent uh permanent of this
1:25guy,
1:26uh its degree is n times d, which was
1:28useful.
1:29Uh
1:30and the point is that A(t) is going to
1:32be um A when t is zero. This is the
1:35permanent that we want to compute A, but
1:37we do it, if you recall, by uh
1:39interpolating through the permanent
1:41values and uh derivatives of permanent
1:43values at uh other inputs other than
1:46zero.
1:48So,
1:49uh we claim that we could set it up such
1:51that
1:52uh for i being 1 through L at these L
1:53points, computing the permanent on these
1:56other locations is easy, where easy
1:59means do it doable in time noticeably
2:01less than this. So, like two to the end
2:02over poly log n.
2:04Um by virtue of the fact that this A of
2:07I has some nice structure that makes it
2:09computing its permanent easy. So,
2:10basically A of I is block diagonal where
2:13the blocks are a little bit small. They
2:15have side length at most n over poly log
2:17n.
2:18Uh plus a
2:20matrix whose rank is like a little bit
2:21small n over poly log n. And you can
2:23compute the permanent of such matrices
2:26and all their submatrices and hence
2:27determinants and things in this much
2:29time and then you interpolate and that's
2:31how we get permanent of A.
2:33So, that was our plan. We got to take A
2:35and find this glorious matrix polynomial
2:37that passes through it where all these
2:39non-zero entries or or values are nicely
2:42structured.
2:44And I claimed we were going to somehow
2:45do it by using this tool which we proved
2:48in the second half of last time, which
2:50was a polynomial
2:53uh in L bits that was good at computing
2:56parity despite being low degree.
2:58So, we found this function G
3:00uh on the L-dimensional hypercube to the
3:02reals.
3:03Um
3:04it's symmetric meaning it's expressible
3:06as just a function of the sum of the
3:08inputs. These Z1s through ZL are plus or
3:10minus one. It's more convenient to use
3:12plus or minus one notation for bits over
3:13here.
3:14Uh Q is a univariate polynomial of
3:16degree D
3:17uh making G also of degree D. And G was
3:20like epsilon close to parity in the
3:22sense that um these two
3:25uh polynomials on the Boolean cube agree
3:27except for an epsilon fraction of
3:29points. And epsilon was like one over L
3:31to the 100. We could make it nice and
3:33big. L is this thing that's around log.
3:35And uh parity in plus or minus one
3:38notation is just a function where you
3:39multiply all the L bits together.
3:42So, it like maybe very slightly bear
3:46some resemblance to this. Not really. Um
3:48but what we're going to do is take this
3:51tool and start using it to build
3:54structured matrices to make it look more
3:57and more like the plan. And while I'm
3:59doing this, you'll be like, "I don't
4:00really know where he's going with this."
4:01But you just got to trust that like
4:02we're getting really nice tool to get
4:04more towards this plan
4:06and we'll finally build up some glorious
4:08um matrix polynomials, not A of T
4:11itself, but some related matrix
4:12polynomials that will help us build A of
4:14T.
4:15And then we'll switch to the other side.
4:17We'll like start from A and try to get
4:19to this A of T.
4:21Yeah.
4:22>> Which one of the new ingredients by the
4:24way?
4:26>> Maybe I mean everything I guess. Yeah.
4:28Yeah.
4:30>> Like this this wasn't known this
4:32paradigm personally.
4:33>> Oh, this was super known. This is
4:34ancient folklore. Everybody knew this
4:35from Yeah, I should have said that.
4:37Everybody knew this in like the 1980s or
4:39something. Yeah.
4:42>> That's for vault symmetric functions,
4:43right? Doesn't have something to do
4:44>> Yeah. Yeah. Yeah. Yeah.
4:47Okay, so let's start
4:49um
4:50extending our use of this uh tool. And I
4:53also might have to like
4:55uh make some things exercises rather
4:57than fully doing them.
4:59Uh okay, so this is a corollary of the
5:01tool. Um for some reason we're going to
5:04want to make variants of this polynomial
5:07where we have a variant that um
5:10doesn't depend on the ith coordinate for
5:12each of the L coordinates. Um
5:16Okay, so just trust me that's going to
5:17be important. So for I'm going to define
5:20>> [laughter]
5:20>> I'm going to define a polynomial that's
5:22like a variant of this G that has like
5:24one extra parameter
5:26T.
5:27Um
5:29and we'll get this by
5:31uh plugging into the univariate Q
5:34uh not the sum of all the Z's
5:38but um just like this funny thing here
5:411 - T over I times ZI summed up.
5:46Okay, so this is a polynomial in in Z1
5:48through ZL and also T.
5:51Um here are all the important things. So
5:53G has
5:55this G has degree
5:57um D
5:59in T.
6:02Okay, because Okay, it's linear in T
6:03here and then we're plugging it into
6:05this degree D polynomial Q.
6:08And if you take T to be zero, you just
6:10get back your approximation to parity.
6:12So, G
6:13uh with T plugged in to be zero
6:16uh is
6:19just parity of Z except that
6:21uh
6:23EPSILON FRACTION INPUTS.
6:30UM BUT THE OTHER FUNNY UH PROPERTY, and
6:33this is going to be towards getting this
6:35structure as you'll eventually see, that
6:36for each of the other interesting
6:39inputs, one up to L,
6:41um you see when T takes on the value I,
6:44this sum end drops out.
6:47So,
6:48uh
6:49G of I
6:51Z doesn't DEPEND ON ZI.
7:00OKAY?
7:04SO,
7:07um
7:12Now, we're going to make like a little
7:13variant of this
7:15uh that's going to look a little
7:16slightly more like this uh pattern
7:18matching speaking.
7:20Uh so, we're going to take F
7:23of T
7:24Z
7:26to be
7:28this G of TZ we just invented.
7:31Um plus like an error term, which is
7:34like parity of Z
7:37minus G
7:40zero Z.
7:44Okay, let's collect up the properties of
7:46this F.
7:50Uh again,
7:52let's say F has
7:54uh degree
7:56D in T. Basically the same as G except
7:59that you add this function that's like
8:01the error, which doesn't depend on T at
8:03all.
8:05Um let's just also say that uh
8:09f of zero
8:11uh z is exactly parity of z.
8:19Uh okay, so we just cooked it up to
8:22this was like the approximation for
8:24parity and we just just sort of like
8:25cooked it up so that we
8:27made f of zero exactly parity up to this
8:29error.
8:31Okay, and so then like this the analog
8:33of this is now like a little bit more
8:34annoying. Uh for i going from one to l
8:40f of i
8:44z
8:45uh it looks like something that um
8:50doesn't depend ON Z I
8:56PLUS SOMETHING THAT'S zero uh
9:01except on
9:04at most epsilon two to the l z's.
9:11Okay, so this is the thing that doesn't
9:12depend on z i when you plug in t equals
9:14i and this is like the fixed thing that
9:17uh is mostly zero.
9:21And maybe you're like, "Okay, I'm sort
9:23of starting to get some pattern matching
9:25feeling here with a i where we have this
9:27like sort of structured piece and this
9:31piece that uh is like somehow mostly
9:34zero."
9:38Okay, so this was
9:40uh
9:41a main step. Any questions about this?
9:45We're going to be like enjoying this f
9:47for a while.
9:49>> [snorts]
9:53>> Okay, so this is uh
9:56some polynomials with some interesting
9:58properties. It's actually like a family
10:00of polynomials where like the zeroth one
10:02is parity and the other I mean the
10:05family when you plug in t being zero
10:07through l, the zeroth one is parity and
10:09the other ones have this like nice
10:11structure.
10:13And our next move is to
10:16turn this F into a matrix polynomial cuz
10:20you know we got to get closer to
10:21matrices.
10:23Um oh, let me just say
10:26not that it's like super important but
10:28uh
10:29I'm going to call this function here
10:32um
10:34E of Z.
10:36It's a function that's only of Z.
10:40Okay. So, here's one way you can do
10:43this. If you're given
10:45um any function on the L-bit Boolean
10:49cube
10:51let me define
10:54uh 2 to the L by 2 to the L matrix that
10:57just puts the truth table on the
10:58diagonal.
11:00>> [applause]
11:02>> Uh D sub H which is like diag
11:07H of Z over all the Zs.
11:11Okay, so um you're going to be thinking
11:13of matrices
11:16that are 2 to the L by 2 to the L and
11:18we're going to like not, you know, name
11:20the rows and columns by numbers between
11:211 and 2 to the L but we'll like name the
11:23rows and columns by
11:25plus or minus 1 to the L.
11:30And this particular matrix that you
11:33build out of a function H you know has
11:35the property that like in the Zth row
11:36and Zth column
11:38you just put H of Z.
11:41Again, there's zeros elsewhere.
11:45Okay.
11:47Uh okay.
11:49So, now we're going to do this to our
11:51our nice function H or F there.
11:55Uh or family of functions F sub T. So, I
11:58want to define
12:00or rather define but we'll look at D of
12:02F
12:03T kind of uh dot if you know what I
12:06mean. So, this is like a different one
12:08of these diagonal matrices for each
12:09value of D.
12:12Uh okay, so this is just
12:14diag
12:16f of t
12:18z
12:19running over all the z's.
12:25Uh, okay, so what properties does it
12:27have?
12:31Well,
12:32uh
12:34So, first of all, this is a diagonal
12:36matrix polynomial in t.
12:39>> [applause]
12:41>> Um
12:43of degree
12:45>> [applause]
12:45>> D.
12:47Okay, and I'll I'll also just write it
12:49like curly D of t.
12:54Uh, and
12:57uh again, it has like a special value at
12:58zero, so curly D at zero is what you get
13:02if you put
13:03just parities truth table down this
13:05column uh diagonal.
13:07And just feel like
13:09explicitly show it uh in the case of l
13:12equals equals three,
13:13uh you have like plus plus plus plus
13:16plus minus plus minus plus plus minus
13:18minus.
13:20OOPS.
13:22>> [applause]
13:24>> OKAY, THAT'S HOW YOU LABEL THE IN L
13:26EQUALS THREE CASE, how you label the
13:28columns. Rows are labeled the same, and
13:30then you put the parity
13:32of this string,
13:34which is uh the product of the entries
13:36along the diagonal, SO IT'S
13:42OKAY, SO THIS MATRIX CURLY D OF ZERO
13:43WHEN L equals three is this matrix.
13:47>> [snorts]
13:48>> And
13:50um
13:52This is a famous matrix, actually. It's
13:53kind of like diag parity,
13:55if you will.
13:57Um
13:58Uh a quantum person would really enjoy
14:00calling this Z, so we'll call it Z as
14:02well, curly Z.
14:05Um okay.
14:07And the last thing, we'll translate this
14:10uh last property of f here. So, for i
14:14going from one up to L,
14:17what properties do we have?
14:19Uh D of curly D of I
14:22is
14:25Well, the first property it's not so
14:28amazingly clear what it is. So, I'll
14:31just
14:32stay say explicitly what it is. It's
14:34just like it's like the diagonal matrix
14:37for some function that like doesn't
14:41depend on the ith coordinate.
14:45So, okay.
14:47Actually, for example, like
14:49let's imagine that I is
14:51three and we're in this L equals three
14:53case. So, it means you kind of like the
14:55truth table down here of a function that
14:56actually happens to not depend on its
14:58third coordinate.
15:00Which means that like these two values
15:01are the same, these two values are the
15:02same, these two values are the same,
15:04these two these two values are the same.
15:06Okay, so it looks like alpha alpha beta
15:08beta gamma gamma delta delta for some
15:10real values alpha beta gamma delta.
15:12Okay, so it's some kind of structure.
15:14Okay, and if like I is one, then it's
15:15like alpha beta gamma delta alpha beta
15:17gamma delta. And if I is two, it's like
15:19more annoying to say what it is.
15:21>> [snorts]
15:21>> Okay, but it's like some kind of
15:23moderately structured diagonal matrix.
15:26And then
15:28uh the other part
15:30is just this DE.
15:32It's the diagonal matrix for this one
15:34specific error function E.
15:37Uh the main thing we know about E is
15:39it's like mostly zero everywhere.
15:42So, it's a diagonal matrix where almost
15:44entries are zero.
15:46So, that's perfect for talking about
15:48rank. You know, the rank of a diagonal
15:49matrix is just the number of non-zeros
15:51on the diagonal.
15:53So, I mean the the cool thing we can say
15:55about this
15:57is indeed the rank
16:00is at most
16:02epsilon times two to the L.
16:05Okay, so these are two to the L by two
16:06to the L matrices. The maximum possible
16:08rank is two to the L and this this
16:09thing's fractional rank is very small.
16:12One over log to the 100.
16:16Okay.
16:18So, okay, now we have something we're
16:20cooking a bit more. We have this matrix
16:22polynomial. It It doesn't match up here.
16:25I mean, not even the dimensions match
16:26up. This is n by n. This is 2 to the L
16:29by 2 to the L.
16:31L is um
16:33Where is L?
16:35It's noticeably less than log n. So, 2
16:37to the L is a lot smaller than n, but
16:39okay, we're we're getting there.
16:41Any Any questions?
16:45Okay, so let's soldier on. So,
16:48uh
16:51That's fine, but now we need to do one
16:54more trick to this
16:57matrix polynomial family to make it
17:00uh maximally useful for executing our
17:02plan. And this may also look a little
17:04bit unmotivated to you, but the final
17:07trick
17:09will involve the Hadamard matrix or the
17:11Hadamard transform. So, I'm going to let
17:14H, curly H, be the 2 to the L by 2 to
17:17the L Hadamard matrix.
17:22Okay, so what is this Hadamard uh
17:24matrix? It's a Boolean Fourier transform
17:26matrix. Uh
17:27we implicitly encountered this before
17:29when we talked about quantum
17:31computation. Remember that like one
17:33second move you could do to your like
17:35array of amplitudes was to literally
17:37transform them by multiplying them by
17:39this Hadamard um matrix. So, some people
17:42are like love this this matrix. If you
17:45uh
17:45study quantum computing, like you learn
17:47about it in lecture one. If you study
17:48analysis of Boolean functions, you learn
17:50about it in lecture one. You study
17:52communication complexity, you learn
17:53about it in like lecture two or
17:54something. You'll see it in Devangee's
17:56video about uh that involves
17:58communication complexity and the inner
17:59product mod two function.
18:00Uh
18:02So, on the other hand, maybe you're
18:03seeing it for the first time. Well,
18:04okay, I just wanted to assure you that
18:06like this is not like come here from
18:07outer space. It's like a well-known
18:09uh tool in many parts of theoretical
18:11computer science.
18:13So, what is this matrix?
18:15Um
18:16So, it's rows and columns
18:19>> [applause]
18:20>> uh it's up to you, but I will choose a
18:22convention will that um
18:25>> [clears throat]
18:25>> I'm going to index them
18:27by
18:290 1 to the L.
18:31You're probably like, wait, you just we
18:33all happy about indexing the Boolean
18:35cube by plus or minus 1 to the L. Now
18:36you're going back to the 0 1 to the L.
18:39Yeah, sorry.
18:41Um, and what is it?
18:43Uh, well, just uh
18:47it's entry
18:49at row U and column V where U and V are
18:520 1 strings
18:54is just a -1 to the U dot V.
18:58Okay, and this is like dot product.
19:02Okay, so it's a matrix full of plus or
19:04minus ones
19:05with like a certain basic pattern.
19:07So, I'll I'll draw the simplest example
19:10of L is 1
19:12then
19:13uh this is a 2 by 2 matrix.
19:17It's rows and columns are indexed by 0
19:19and 1 and you get +1 +1 +1 -1.
19:23Okay, I guess Jacques Hadamard invented
19:25this matrix in the 19th century and
19:27that's why it's named after him.
19:32Okay.
19:36Uh, but we'll go back to L equals L.
19:39And
19:41now let's define yet another like cool
19:44matrix family.
19:46Uh
19:49Okay, I'm going to erase this just to
19:50have some room.
19:57So, I'm going to define
20:00finally, uh
20:02this is going to be our really truly
20:03important matrix polynomial. That's the
20:05J
20:06J of T
20:08is um some scalar which we don't worry
20:10about too much 2 to the minus L
20:12times uh Hadamard times
20:15uh curly DFT times Hadamard.
20:19Okay, so it's sort of like the Fourier
20:21transform in some sense of this
20:24matrix polynomial.
20:27Okay. And now, like we have to go
20:29through these
20:31cool properties of of curly D and see
20:34what cool properties of curly J that we
20:36get out of them.
20:39Uh
20:42Okay. Well,
20:44capital H here is just a just like a
20:46scalar
20:47matrix. So, if you multiply it on both
20:49sides, it doesn't change the degree.
20:52So, this is also a matrix polynomial of
20:55J of T
20:59of the same degree as that of G D, which
21:01is
21:02D.
21:05And what is J of zero?
21:11Uh well, it's it's
21:14two to the minus L
21:16Hadamard and then
21:18the special parity matrix Z
21:21Hadamard again
21:23uh which is also like a very famous
21:26simple matrix
21:27which I'll call curly X.
21:30In a moment, I'll tell you what this is,
21:31but it's a very simple and enjoyable
21:33matrix.
21:35And the quantum enthusiasts already know
21:37what it is, I guess.
21:39Or the analysis of Boolean function
21:41enthusiasts.
21:43And finally,
21:44let's do this last
21:46one. So, for
21:49I between one and L as always is
21:52what's up with
21:53J of I?
21:56>> [snorts]
21:57>> Okay. Well, it's of the form
21:59two to the minus L H and then
22:03um
22:04some
22:05diagonal thing that doesn't depend on
22:07I's coordinate
22:12times H and
22:16Okay, matrices like this are going to
22:19have some kind of structure and we'll
22:20talk about that too. They are also like
22:22a little bit pleasant. You You so for
22:24example, when I three, we said like
22:27these D matrices look like alpha alpha
22:29beta beta gamma gamma delta delta.
22:31And if you wrap Hadamard's on both
22:33sides, we'll see you get some
22:36somewhat pleasant structure to the
22:37result. It's some kind of sort of block
22:39diagonal matrix.
22:41So, we'll come back to that.
22:43And then,
22:45uh
22:45over here, we're wrapping this specific
22:47diagonal matrix of low rank
22:50with some Hadamard's.
22:52And we'll just use the fact that we have
22:53a matrix of low rank and you multiply by
22:55another matrix, the rank cannot go up.
22:57It can only go down.
22:58So, we'll just use that this new matrix,
23:02which I'll call E prime,
23:05it's not the same thing as E. They have
23:06different dimensions and things, but
23:08we're getting there. This is low rank.
23:21Okay, so we're making more progress.
23:23This This This
23:25family J is
23:28going to be really helpful to us for
23:30executing the plan.
23:32And,
23:33uh
23:34this fine enough to tell you like what
23:36is this script X and like what is the
23:38nature of these matrices.
23:43Any questions?
23:47Okay, take a cell phone photo of this
23:48plan if you forget it because I'm going
23:50to erase it in in 1 second.
23:52>> [laughter]
23:53>> Uh Oh, you're really doing it. Okay,
23:55cool.
23:56Uh okay, great.
23:59All right. Yeah, we can all take a
24:00break.
24:02Uh okay, so, um
24:05>> [snorts]
24:05>> basically, and
24:07just so I don't run out of time, I may
24:09skip some calculations, even though
24:11these calculations are extremely easy
24:13and pleasant. I don't know, maybe I'll
24:15do one.
24:16Um but, you know, the whole theory of
24:18analysis of Boolean functions like kind
24:20of tells you things about what happens
24:21when you, you know, do a Hadamard
24:23transform to
24:26a function.
24:28And so, I'll I'll tell you
24:31like what's up with this matrix and
24:32what's up with these matrices.
24:35Uh okay. Well, now we have like a bit of
24:39a thing where we're like, well,
24:41but you decided to index this guy with 0
24:431 to the n, but this guy with plus or
24:45minus 1 to the n. Like the time has come
24:47that we have to resolve this. So, we're
24:49going to resolve this by um switching
24:52the the indices here. So, uh let's let's
24:56now index
24:58uh these rows and columns
25:03>> [applause]
25:05>> by uh 0 1 to the n.
25:10Okay, so we just have to like, you know,
25:11now in our mind we're like, oh, now it's
25:13like 0 0 0, 0 0 1, and and so forth.
25:18Um
25:19okay, which means that uh Z
25:22uh to
25:24Y Y
25:27it's like the So, this is a 0 1 string.
25:29We have to express the parity of it in
25:32plus or minus 1 notation once again. So,
25:33it's This is like minus 1 to the Y1 plus
25:37dot dot dot plus Y
25:39L.
25:40And uh
25:41this is 0 else.
25:43>> [applause]
25:44>> Yep.
25:45>> Is Is it 0 1 to the L?
25:47>> Sorry, 0 1 to the L. I have like a very
25:49bad habit of just assuming in in doing
25:52Boolean functions you always have n
25:53bits, but we have we have L bits.
25:54Thanks.
25:56Uh okay. So, this is the same thing is
25:58I'm just saying this is the same thing
25:59as this when you These stay plus or
26:01minus ones, but the indices change to 0
26:041 notation.
26:05Okay, so this exponent here is actually
26:07computing 0 mod 2 plus or minus 0 mod
26:12Sorry, it's computing parity up to mod 2
26:14and then you do minus 1 to that.
26:17Okay, that's fine.
26:20Okay, so uh
26:22in both these cases we have like a
26:24slightly special form. We have like
26:25Hadamard times a diagonal matrix times
26:28Hadamard
26:29times a scalar.
26:30And if you literally just write down the
26:33formula for matrix how like matrix
26:35multiplication works,
26:36um you don't really get like double sum
26:39ends because this thing is like a
26:41diagonal matrix. So, I'll I'll simply
26:43say it's an exercise for you that if you
26:46have uh literally any
26:51real valued Boolean function,
26:53uh then you have this formula, this 2 to
26:56the minus L times Hadamard times that
27:00the diagonal matrix built out of F times
27:03Hadamard.
27:05This thing,
27:07it's UV entry is
27:10Should have given myself more space.
27:13Uh expectation over a random Y
27:18of minus one
27:20to the U plus V
27:23.Y
27:28.Y times f of Y.
27:36Okay. So, I mean this expectation cuz
27:38you have this 2 to the minus L here and
27:40then
27:41basically only need like one sum end
27:42across the rows and columns cuz this is
27:44a diagonal matrix and you kind of get
27:47minus one to the U.Y because of uh
27:51this and you get minus one to the V.Y
27:54also because of this and f of Y.
27:56Okay.
27:58And
27:59uh yeah, this also should remind you
28:01sort of of the formula
28:03for
28:05you know, changing the amplitudes and
28:06the little bit we said about quantum
28:08computation.
28:12Okay.
28:13So, this is a convenient formula and for
28:15example, we can now uh find out what
28:18this
28:19uh cool
28:21X matrix is
28:24because, you know, we exactly have Z and
28:26Z is diagonal
28:28uh this. So, just plug this
28:31in for F here and I assure you you'll
28:35get the following.
28:37Uh
28:38this
28:39script X is maybe what you might call
28:41the anti-diagonal matrix.
28:44>> [applause]
28:48>> Um it's sort of like the identity matrix
28:50except like going like this, it goes
28:51like this.
28:53And
28:54uh another way to say it is that um
28:59it has a one
29:03uh
29:04when like the row and columns are
29:06bitwise negations of each other.
29:09Okay, this means like the bitwise
29:10negation of this string.
29:11And it's zero otherwise.
29:20Okay, and probably while I'm talking you
29:22can
29:23uh prove this in your head. So, you plug
29:25this, which is like minus one, this is
29:28like
29:29minus one to the like all ones vector
29:32{dot} y, I suppose.
29:35Okay, if you plug this into this
29:38and do a two-second calculation that
29:39like the expected value of negative one
29:42to
29:43uh
29:44a dot product is one if this is like
29:47always zero, and if it's not always zero
29:49then everything cancels and you get
29:50zero.
29:55Okay, so that's that.
29:58And then
30:00ooh.
30:01I'm going to erase this last bit to just
30:03cram things in, but hopefully that's
30:05okay.
30:06And then exercise two
30:10is to understand the nature of these
30:11matrices. So, it's like saying, "Oh, if
30:14this F
30:17has the property that it doesn't
30:19actually depend on the ith coordinate
30:22then you get something kind of simple
30:24here, or like rather
30:26if this means that like f of y equals f
30:28of y prime whenever they differ on the
30:31ith coordinate
30:32then you get like some cancellations
30:35here.
30:37And I'll just tell you what it turns
30:38into, but this is also a simple
30:40exercise.
30:42Um
30:44if you have some matrix M that looks
30:46like this, 2 to the minus L H
30:49uh a D where it doesn't depend on I's
30:52coordinate
30:56uh times H again.
31:00Then M is
31:04what I'll call
31:06I's
31:07coordinate
31:09block
31:11diagonal.
31:15That's a term I'm defining here.
31:17And what does that mean?
31:20Uh
31:23it just means
31:25that um you have a bunch of zeros in
31:26certain places. If UI differs from VI
31:31then MUV is zero. I'll draw a picture in
31:34a second.
31:40Okay, so as I said, you prove this by
31:43um showing oh, if U and V are two
31:45strings that differ in the I's
31:47coordinate, then this thing has a one in
31:49the I's coordinate
31:51which means that like when you dot it
31:52with Y, like YI is really like active in
31:55this exponent.
31:57So, you get plus or minus when you vary
31:59it, but then when you vary it these
32:00things it doesn't change, and that's why
32:01you get zeros.
32:05Let's try to like
32:07get a mental picture for this property.
32:10Uh I's coordinate block diagonal. So, I
32:13have conveniently like a 3 by 3 matrix
32:15over here.
32:17Um so, let me try to illustrate it.
32:21Okay, so again now the rows and columns
32:23are indexed by binary strings, so we got
32:25like 000, 001, 010, 011, 100, 101.
32:34Okay, the same in the rows.
32:39etc.
32:40Uh okay, so
32:42uh
32:43let's look at um third coordinate block
32:45diagonal. So, let's say third coordinate
32:47block diagonal.
32:58Okay, so that means you have zeros in
32:59certain locations. Like if your row and
33:02column indices differ on the third bit,
33:06then you have to have a zero.
33:08So, let's see.
33:10So, that means like
33:11um
33:15Let's see. So, here
33:17Oh, maybe we should do first coordinate
33:18block diagonal first.
33:20Is that better? Yeah, let's do first
33:22coordinate block diagonal. So, that
33:23means here 0 0 0. Uh you've got to have
33:25zeros whenever like the first coordinate
33:27of the row is
33:29one. So, you have to have like zeros
33:30here.
33:310 0 0 0. And this also starts with a
33:34zero, so you also have to have zeros
33:35here. This also starts with a zero. This
33:37also starts with a zero. So, this whole
33:40like top right you need to have zero.
33:43And similarly, these row indices all
33:44start with one. These ones all start
33:46with zero, so you have to have zeros
33:48here.
33:49There's no other restriction, so like
33:50this is star.
33:53Okay, so uh first coordinate block
33:55diagonal matrix is block diagonal that
33:58looks like this. Okay, now hopefully
33:59you're again like uh
34:01I can look at my phone, the plan like it
34:02has something about block diagonality on
34:04it. Like we're we're kind of getting
34:05there, you know?
34:07Um
34:09Maybe I'll ask you like what is
34:11at high level what does
34:13third coordinate block diagonal look
34:14like in this picture?
34:18Not that it's really important, but just
34:19to see if you're following along.
34:31Maybe it's hard to look at when I have
34:33content in here.
34:36>> [snorts]
34:41>> Okay, where are the forced zeros in the
34:43first row?
34:44>> [clears throat and cough]
34:46>> Every other one, yeah. So, like this one
34:47has to be zero, this one has to be zero,
34:48this one has to be zero, this one has to
34:50be zero. This ends in a one, so you have
34:51forced zeros
34:53uh when this guy has a zero at the end.
34:55So, zero zero zero zero. These ones are
34:58not forced.
35:03And actually then the pattern repeats
35:04like uh this ends in a zero, ends in a
35:07one, ends in a zero, ends in a one, ends
35:08in a zero, ends in a one. So, like uh
35:10it's checkerboard.
35:12Okay, so like each of these two by two
35:14blocks
35:16is diagonal.
35:19Okay, and then second coordinate block
35:21diagonal is annoying looking, but
35:24uh
35:25if you rearrange the rows and columns
35:26here to like change, let's say, the
35:28second coordinate into the first
35:29coordinate, which is like the most
35:31enjoyable coordinate, it means it's it's
35:33block diagonal in the nice way. Okay, so
35:35in particular, all these conditions mean
35:37that like
35:38there's a natural way to rearrange the
35:39rows and columns so that it looks like
35:42maybe the most pleasant
35:45notion of block diagonal, which is
35:47this one.
35:52Okay. So, great.
35:56So, now
36:00we will
36:03use these facts that we've learned
36:07to summarize everything we know about
36:08this polynomial family uh J of T. And
36:12this will be like our final bit of like
36:15messing around with matrices and then
36:16we'll like go back to the plan.
36:18Okay, so
36:20like our final glorious theorem
36:25re matrices
36:27uh yeah.
36:31Okay, so we have this like uh I'll just
36:32call it it's not too magic, but just so
36:35it's like a memorable adjective
36:36associated to it, we have a magic uh
36:41matrix polynomial.
36:45Uh
36:46matrix polynomial
36:48>> [applause]
36:50>> indexed
36:53by 0 1 to the n.
36:56Sorry, L.
36:58Um and has these properties, degree
37:03in T is D, which is this uh
37:07root L log L.
37:11And
37:12uh
37:13at zero it's this like anti-diagonal
37:15matrix X.
37:18>> [applause]
37:25>> Okay, and finally
37:28J I and this is as usual for I between 1
37:30and L.
37:33Um has this nice form, which I'll call
37:36like B I prime plus E prime.
37:40Uh where the good thing about E prime is
37:42it's of low rank.
37:44The rank is at most now
37:48plug in the actual value for epsilon,
37:49which is 1 over L to the 100 * 2 to the
37:51L.
37:53And the cool thing about this thing is
37:55that it's
37:57I coordinate block diagonal.
38:02>> [applause]
38:06>> Okay.
38:10Okay, so we have now
38:13discharge like all our work about the
38:15initial tool, the low degree polynomial
38:18that approximates parity.
38:20The whole purpose of it was to get this
38:23glorious
38:25matrix polynomial
38:27J F T.
38:30Which has the property that looks like
38:31this very special matrix X at zero,
38:34>> [snorts]
38:34>> which is sort of like the least
38:36block diagonal matrix, like
38:38um
38:39I don't know, it violates I block I
38:42coordinate diagonality for all I.
38:45But if you like go to all these other
38:46points where I is between 1 and L,
38:49it is basically I's coordinate block
38:50diagonal
38:51except for a low line low rank matrix.
38:57Okay.
38:58We're halfway done.
39:00Any questions?
39:03>> [snorts]
39:04>> Now, we go back to the plan.
39:07Let's stick with the plan.
39:09As they say in Survivor.
39:17Okay, so I'll briefly remind you of the
39:18plan.
39:23Uh
39:24we're given
39:26this like n by n matrix A
39:29and it has like order one
39:32non-zeros per row and column.
39:35So, it's sparse like that.
39:38You can make this order one three if you
39:39want. So, I'll just imagine it's three,
39:41but it also doesn't matter.
39:43Um
39:45and we want
39:48uh
39:50MATRIX POLYNOMIAL
39:52>> [applause]
39:53>> A OF T
39:56uh
39:57such that
39:59for
40:00L
40:02in this
40:04log n over log log n
40:07>> [applause]
40:09>> um the degree of A of T
40:13should be at most basically root L.
40:19And A of zero should be A.
40:23And finally
40:25again, for I between 1 and L
40:30A of I should have some nice structure.
40:32So, A of I
40:33should be expressible as B I
40:36plus E
40:38where this one has rank
40:42at most n over poly log.
40:48And this one is a block diagonal
40:51>> [applause]
40:54>> with blocks of dimension at most n over
40:57poly log.
41:06And because these kind of matrices are
41:08easy to compute their permanents
41:10in like two to the n over poly log time.
41:15Okay, so obviously we're going to be
41:16using this this J to pull it off.
41:19>> [clears throat and cough]
41:21>> So,
41:22yeah, I mean here's like an interesting
41:23part of the whole story which is
41:26you might think
41:28A literally has absolutely no structure.
41:31So, how in the world are we going to
41:32turn it
41:34or how are we going to get this like
41:35polynomial
41:37family
41:38that equals this completely unstructured
41:40matrix A at zero, but like all the other
41:42values have this nice structure.
41:45And all I can say is like, well,
41:48there is one teeny tiny way in which A
41:52actually does have structure.
41:54And it's this. It has, you know, maybe
41:58three non-zeros per row and column.
42:00And like that's like the one thing that
42:01we're really going to grab hold of to
42:03make some progress.
42:06So,
42:08we're definitely going to want to start
42:10viewing matrices A as like the incidence
42:13matrix of n by n plus n bipartite
42:16graphs. As is kind of standard.
42:18So, we can picture A like this.
42:21You got like a bipartite graph.
42:23n vertices on each side.
42:29Okay, for one second imagine A's entries
42:31are zero and one. So, it's really the
42:33incidence matrix of a bipartite graph.
42:35Okay, so [snorts] the fact that it has
42:36at most uh
42:38constantly many non-zeros per row and
42:39column means this is like a bounded
42:41degree graph. Let's just imagine it has
42:42degree three. You can reach that exact
42:44case if you like. Um okay, so every
42:46vertex has on the left this degree
42:48three. Every vertex on the right also
42:50has degree three.
42:52Uh okay, so this is how we can picture
42:55A.
42:56And uh if A doesn't have zero one
42:58entries, it's okay. Just think of a
43:00weighted graph where like the weight on
43:02an edge is the entry.
43:07Okay.
43:09So,
43:10um
43:12we want to make this a bit more
43:13structured using the fact that
43:16um
43:19you know, it has constant degree.
43:22So,
43:24let's imagine that you
43:27bucket the left and right vertices
43:29SEPARATELY
43:32>> [applause]
43:36>> INTO
43:38UM ABOUT square root n buckets.
43:42Let's say 10 root n buckets.
43:46>> [applause]
43:47>> How are you going to do this? Well, I'll
43:48say in a second, but first, this is not
43:51exactly what you do, but just imagine
43:52you bucket them randomly. You put each
43:54vertex into on the left into like one of
43:57B buckets randomly and on the right
43:59randomly.
44:01Um notice that you have
44:04uh
44:04B squared
44:07equals 100 n BUCKET PAIRS.
44:13UH LIKE CHOICES FOR A BUCKET ON THE LEFT
44:15and a bucket on the right, and that's
44:16much more than the number of edges.
44:20Because I guess the number of edges is
44:21like three times n.
44:25So,
44:27if [clears throat] for example, you
44:27bucketed randomly,
44:29you might like hope that um every edge
44:32was in a like a different bucket pair.
44:34Like if the bucket pair of an edge is
44:35like the bucket of its left end point
44:37and the bucket of its right end point.
44:38Actually, that's probably not true
44:40because of like some collisions or not
44:42collisions, but there'll be like a
44:44little bit of collisions.
44:46But actually, I mean the randomness is
44:47just for a like a little bit of thought
44:48experiment. Um you can actually choose
44:51the buckets simply so that this
44:54literally happens.
44:55And uh you just have to use the greedy
44:57algorithm. So, I will just
44:59also leave this as an exercise, but
45:02there's like a simple deterministic
45:05algorithm
45:07TO BUCKET.
45:11UH JUST LET ME DRAW A PICTURE HERE.
45:14Like
45:15I don't know some
45:17Of course, they're not the buckets are
45:18not going to actually be contiguous, but
45:20um you know, you can rearrange your
45:21graph after you've done the bucketing so
45:23that they become contiguous.
45:25Uh
45:27such that um
45:29you have uh
45:31EACH BUCKET PAIR
45:37HAS AT MOST ONE EDGE.
45:42OKAY, SO actually for example, it won't
45:43actually look like this because here we
45:44have like a bucket pair of first bucket,
45:46first bucket that has two edges. Maybe
45:48I'll erase that.
45:49Um possibly there's some other
45:52counterexamples in this picture, so let
45:53me actually
45:54draw a better picture.
46:05Um
46:07So, I'll just draw the buckets here.
46:08This is a bucket,
46:09bucket, bucket,
46:12bucket, bucket,
46:15bucket. This is like bucket number one,
46:17bucket number two,
46:19da da da bucket number B is down here.
46:22It's bucket number one,
46:24bucket number two,
46:25bucket number B is down here.
46:28And uh let's say between bucket two and
46:30bucket one you have like exactly one
46:32edge. I want to draw the edges in color,
46:34so let me try to
46:36do that. Um let's say between bucket
46:39number one and bucket two two you have
46:40like exactly one edge.
46:42And between uh I don't know, bucket two
46:46and bucket one you might have like
46:47exactly one edge. Never more than two
46:50edges.
46:51And maybe you have like some edge up
46:53here.
46:56And actually for some mild reason, which
46:59is not super important, I actually want
47:01to not have any edges that go from
47:04between same-numbered buckets.
47:06Okay, this is like a very minor
47:07constraint, but like I'll just say also
47:11no edges
47:14in like BB bucket pairs.
47:20Okay.
47:21Um
47:23Yeah.
47:27Uh okay. So, you know, all the vertices
47:29still have degree three on the left and
47:30the right, but we have this situation.
47:34And
47:37let me do one other like super minor
47:39thing, which is again, this is just for
47:41like notational convenience, but it's
47:43totally possible that some bucket pairs
47:44will have zero edges between them, like
47:47uh well, we we enforce it for like 1 1 2
47:492 3 3, etc. But, it's also possible
47:51there might not be any edge between
47:53three and two.
47:54In that case, just put an edge
47:57and uh give it weight zero.
47:59Okay, let's just it'll be like kind of
48:01convenient to be able to say that like
48:02for all bucket pairs other than this
48:03one, you have exactly one edge.
48:06Okay, and like put the zero-weight edge
48:12edges if needed.
48:17So, that I can say they have like
48:19exactly one edge.
48:24Uh okay, another way to think about it
48:26is if you now imagine what A looks like
48:28after you kind of reorganize its rows
48:31and columns into buckets, it also has
48:33like a block structure
48:35where it has zero blocks on the
48:37diagonal, that's this fact,
48:39and in every other block, uh you have
48:42exactly one non-zero.
48:45Well, except for these like fictional
48:46zeros, whatever.
48:48Um
48:50Moreover, the blocks have very small
48:52dimension, right? The block sizes
48:55Oh, I forgot to say this as well.
48:58You have to make sure that these are
48:59about the same size.
49:07Okay, so it's still part of this greedy
49:09exercise. You can also make sure that
49:11like all the
49:13buckets
49:15have size about n over capital B, which
49:17is also like root n.
49:19Okay, so in this this block
49:21matrix version of A that I'm imagining,
49:24um these blocks have dimension about
49:27square root n.
49:32Okay.
49:35Any question?
49:37Okay, so we've got like a little bit of
49:39structure out of capital A now.
49:42And now we're going to try to like jam
49:46this structure into the picture.
49:50So this next
49:53bit
49:54eh
49:56may look a little unmotivated, but it's
49:59motivated by trying to jam this glorious
50:02theorem into the picture.
50:10So
50:12>> [snorts]
50:12>> I now want to turn this into a
50:16tripartite graph
50:18where I have some middle vertices.
50:21And [snorts] the middle vertices, uh
50:23hopefully I can not ruin this diagram.
50:27Okay, I'm going to have like m equals b
50:31times b minus 1. That's the number of
50:33bucket pairs, middle vertices. The
50:34number of bucket pairs other than this
50:35kind.
50:37I'm just going to stick them in here.
50:40I'll redraw this in a second.
50:42>> [clears throat]
50:44>> And these are going to name the bucket
50:46pairs. 1 2
50:482 1
50:501 3
50:523 1
50:54I don't know, like b b prime such that b
50:56and b prime are different, etc.
51:01And
51:02uh
51:03I [clears throat] also want to order
51:04them in this way where a bucket pair and
51:06its reverse come consecutively.
51:11So, I want to just
51:13change this. So, right now this this
51:16bipartite graph I've Okay, forget I
51:18inserted these vertices in the middle.
51:20This bipartite graph is literally the
51:21edge incidence matrix for A.
51:23And what I'm about to do here is to make
51:24a matrix factorization
51:27where A equals L * R where L is going to
51:32be
51:33the
51:34uh incidence matrix for this left
51:36bipartite graph and R is going to be
51:38this incidence matrix for this right
51:39bipartite graph.
51:41And here's how I I want to do it. You
51:43see
51:46here this edge this green edge goes from
51:48bucket one to bucket two. I'm just going
51:49to make it pass through a vertex one
51:51two.
51:52Okay, so I'm going to
51:53put this
51:55and then
51:56uh
51:57this.
51:58Okay, and then I'm going to erase this.
52:03Okay? And then this purple edge
52:07you know, you just hop straight from
52:09this vertex
52:10uh in bucket two to this vertex in
52:11bucket one. I'm going to not let you hop
52:13straight there. I'm going to like have
52:15you pass through two one.
52:20And I'll show it also for the orange
52:22one.
52:23So, orange was going from uh bucket
52:25three to bucket one. So, I'm going to
52:26have it
52:28pass through three one.
52:34Okay, and so forth.
52:36So, uh I'm going to do that um to make
52:39this tripartite graph. And
52:41um I want to claim that like all the
52:44paths you had before from left to the
52:45right, they were positive length one.
52:47They're like uniquely identified with
52:48paths from the same left vertex to the
52:50same right vertex in this story.
52:53And so, if L is like what matrix
52:55multiplication means, if L is the
52:56incidence matrix for this thing and R is
52:58the matrix incidence matrix for this
53:00thing, then you factorize A equals L *
53:02R.
53:04Well, I guess I told this story as
53:06though all the edges had weight one.
53:08Um but you know, if this green edge used
53:11to have some weight
53:12alpha, then
53:14whatever, you can put the alpha here and
53:16the one here, and now the product along
53:18this is alpha again. So, you can put
53:19like all the weights, let's say, in the
53:21left bipartite graph and put all one
53:24weights in the right bipartite graph,
53:26and you're you're fine.
53:28Okay? So, we've just taken this and
53:30like,
53:31you know, given like a little bit more
53:32structure. Now, it is factorized this L
53:34times R.
53:36And just to think about the degrees
53:37again, like every vertex on the left
53:38still has degree three. Every vertex in
53:41the middle has degree one to the left
53:42and degree one to the right. It's very
53:44simple because each bucket pair has
53:46exactly one edge. So, it's degree one to
53:48the left, degree one to the right.
53:51Okay.
53:56Now, we're going to make it weirder.
53:58Okay.
53:59So, uh
54:01this is
54:02hard to uh explain,
54:05but I want to take this picture
54:08and I want to make it quadripartite. I'm
54:10going to like have an another middle
54:12layer of vertices
54:14in the middle.
54:16And for whatever reason, I really want
54:18X's down the middle of this picture. So,
54:21I'll explain what I mean by that. So,
54:22we're going to have uh
54:26These are the middle vertices like
54:28before.
54:29This is like one, two,
54:31two, one, one, three, three, one.
54:36Oh man, I should have I should have I
54:37shouldn't
54:38mess it up too much like that. Uh we're
54:40going to have another copy, so it's like
54:41one, two,
54:43two, one,
54:46uh
54:47one, three, three, one, four, four, one.
54:50And we're going to fill up the same
54:51buckets.
55:01Okay, and I'll just tell you my weird
55:02goal. My weird goal is I want to like
55:05again have a picture that exactly
55:06captures this exact same thing. Like
55:08it's originally literally equivalent to
55:10A. I'm just going to make these paths do
55:12like a further like weird thing in the
55:14middle.
55:15And
55:16because of
55:18this X,
55:20I just insist that I want the middle
55:22layer to look like a bunch of X's.
55:32There's actually a more normal thing I
55:33could have done here. I could have made
55:36these look like a bunch of parallel
55:37edges. And then I wouldn't have to do
55:39anything. I would just like take this
55:40picture and like take these vertices and
55:42just like make two copies and have a an
55:44edge. And that would be the same as
55:46inserting the identity matrix here.
55:49Because like then
55:51the matrix for like going straight
55:53across is the identity matrix.
55:56But for some weird reason, I really want
55:58the X's in the middle.
56:00So, okay. So, I just make it happen. Um
56:05Formally, I think
56:07uh you can do it by saying take this
56:10matrix R,
56:12it's an M by N matrix, and like
56:14interchange all consecutive pairs of
56:17rows,
56:18and then stick an X in the middle, and
56:21it works.
56:22I'll try to do it in a picture.
56:25So, it's just like Okay, we used to have
56:27this green path and we want to keep it
56:28alive. So, it started here and it went
56:31to like one two. But now it's supposed
56:34to end up in like bucket two,
56:36but like it's sort of forced to go here.
56:38So, we just I mean, we set it up so that
56:40it looks like this. Okay?
56:43And then like the purple one like it
56:46went up here, it went to two one, and
56:48then it was supposed to go into the
56:49first bucket, and it it went up here,
56:52and go like here.
56:53>> [clears throat]
56:54>> Try to do the orange one.
56:56Went up to three one.
56:58Uh
56:59This
57:00Yeah, yeah. That's this one maybe.
57:03And then like I force it to go here, but
57:05really it was supposed to go into here.
57:06So, okay, it goes like that.
57:08>> [snorts]
57:10>> Um
57:12Okay. So now like I guess that like it
57:14used to be that like this vertex was
57:18connected to 2 1 if
57:21um in the original graph
57:24uh it was in bucket one and its unique
57:27edge
57:28uh
57:31was in bucket two. And anyway, we just
57:34like reverse this convention here.
57:37Okay, so
57:39uh
57:40As I said, what you really do is I mean
57:41if you think about it for a little
57:42while,
57:44uh
57:45this is kind of the same thing as the
57:47original R, but maybe every consecutive
57:49pairs of rows is interchanged.
57:52And then [snorts]
57:53this matrix, well, I'll get back to it
57:55in a second. This is still literally L.
57:58And we've achieved this factorization.
57:59And what is this matrix?
58:02It's
58:03diag
58:05X X
58:08X.
58:10So what do I mean by that?
58:13Oh boy.
58:17Yeah, I'm going to erase this.
58:25Okay, so
58:28this MIDDLE MATRIX
58:32THE INCIDENCE MATRIX FOR ALL THESE like
58:34X's that I decided to force in there.
58:37What does it look like?
58:40Well,
58:41its rows and columns is like M by M.
58:44Rows and columns are like 1 2 2 1 1 3 3
58:491 etc.
58:521 2
58:542 1 so forth.
58:56And it's it's naturally divided into
58:58like 2 by 2 blocks
59:00corresponding to a bucket pair and its
59:01reverse.
59:03And uh I mean there's mostly no edges
59:05going from the left to the right here,
59:06but so this is actually all zeros. This
59:08is all zeros. And then each little
59:11matrix here
59:13is this
59:15crossing matrix. This This little matrix
59:17here is capital X, this 2 by 2 matrix.
59:21So, yeah, this is the matrix for like
59:23this middle bipartite graph.
59:25Okay, and with the more natural thing
59:26where I just made all the edges go
59:27across, like these would all be 2 by 2
59:29identity matrices, and then actually the
59:31whole thing would be an identity matrix.
59:38Okay, now
59:40Any questions besides why did you do
59:42this? Or yeah.
59:47Okay.
59:50Oh, boy.
59:51I need more space.
59:54Uh okay, I'm going to erase this. So,
59:57we've got to here.
59:59Yeah.
1:00:01Oh, well, anyway.
1:00:02So,
1:00:03here's the thought experiment. Like this
1:00:05is still A, but remember what are we
1:00:07trying to do? We're trying to make
1:00:08variants of A
1:00:10The plan says you're trying to make
1:00:11variants of A that have like more
1:00:12structure in them, and hopefully also
1:00:15the permanent of your variant is related
1:00:17to the permanent of A, but let's just
1:00:18think about the first question of like
1:00:20let's make a variant of A that has more
1:00:21structure.
1:00:23So,
1:00:24thought experiment.
1:00:29>> [applause]
1:00:31>> UM
1:00:33CHANGE
1:00:36ALL the X's in the middle
1:00:42to I's.
1:00:45That's
1:00:462 by 2 identity matrices. So, in this
1:00:48picture that I just hopefully erased,
1:00:51you know, I had all these like 2 by 2 X
1:00:52matrices on the diagonal, just imagine
1:00:54changing them all to I's.
1:00:56Okay, so
1:00:57uh
1:00:59can I do this?
1:01:01Okay, let me try to do this
1:01:03here. It's going to be terrible, but
1:01:07Okay.
1:01:08Well, I'll I'll do it a little bit. So,
1:01:10it's like we're going to like uncross
1:01:11all these middle guys. So, let me just
1:01:13uncross this one for a moment.
1:01:17Like I changed it to an I.
1:01:20And
1:01:22you know, this is going to become down
1:01:23here.
1:01:24I guess what I'm imagining is like you
1:01:26consider A sub new, which is L times
1:01:29diag
1:01:31I I da da da da I
1:01:34times this R
1:01:36prime.
1:01:39And
1:01:41yeah, this one maybe I'll also imagine
1:01:43changing to straight across.
1:01:46And let me ask you now,
1:01:49what kind of structure will this A new
1:01:52have now that we've put these cross
1:01:53uncrossed
1:01:55yellow edges in?
1:01:57Like in the final matrix, which this
1:02:00final matrix of course is expressing
1:02:02its vertex, its rows are this, its
1:02:05columns are this, and
1:02:07an entry is expressing the
1:02:10the number of ways to get from this
1:02:12vertex to that vertex or
1:02:14the weight of ways to get from this
1:02:16vertex to this vertex.
1:02:17So, what kind of structure does it have
1:02:19or do you notice anything about its
1:02:20structure?
1:02:23>> It would be almost symmetric.
1:02:26>> A
1:02:28little bit, in what sense?
1:02:29>> Uh the entries
1:02:32Uh the entries
1:02:34are the same.
1:02:36>> Is
1:02:37that so? Yeah, well, it's an undirected
1:02:42Is that right?
1:02:43Um
1:02:48Uh [groaning]
1:02:50I think that's true. Well, maybe except
1:02:52for the fact that there's weights, but
1:02:53yeah.
1:02:58Um maybe it's hard to tell.
1:03:01Uh
1:03:05I guess what I'm going for is it's
1:03:07actually kind of block diagonal. Like
1:03:09bucket one here, if you start here,
1:03:11which is in bucket one, you go across,
1:03:14you end at bucket one. If If here in
1:03:16bucket two, you go up, you go across,
1:03:18you end at bucket two.
1:03:20And okay, this this one we didn't draw,
1:03:22but um
1:03:25it's the same thing.
1:03:28>> [snorts]
1:03:28>> Uh
1:03:30So, that's the nature of this. So, if
1:03:33you do that, then maybe with like more
1:03:35pictures it would have been good, but
1:03:38uh
1:03:40and A new
1:03:44is block DIAGONAL
1:03:49WITH RESPECT
1:03:52TO the buckets.
1:03:55>> [applause]
1:03:59>> Okay, so like it used to be that like A
1:04:01you know, maybe before you like the
1:04:02buckets were like this.
1:04:04We used to have the situation where this
1:04:05was zeros, and then we had like one one,
1:04:08or I suppose one non-zero in each thing
1:04:10here.
1:04:11And like A new
1:04:15uh is actually going to be
1:04:21like this.
1:04:25Now, these entries are not going to be
1:04:26like they're going to be like sums of
1:04:28entries in here. So, these will not like
1:04:30have just one one, but it'll look like
1:04:32this shape.
1:04:35>> [sighs]
1:04:36>> Um
1:04:39Maybe we should do one more example.
1:04:40Let's see. So, like
1:04:42perhaps [snorts]
1:04:44uh
1:04:46Okay, hopefully I don't botch this on
1:04:48the spot. 1 2 2 1
1:04:511 3 3 1
1:04:55Uh oh, maybe like this was 1 3.
1:05:00So, this guy has degree one.
1:05:02Um
1:05:03uh to the left. So, it means it's coming
1:05:05from like the
1:05:07original edge
1:05:08that went from bucket one to bucket
1:05:10three. So, maybe in the original
1:05:12original A there was like some reddish
1:05:14edge that went from one to three.
1:05:17Um
1:05:19So, we did this.
1:05:21Uh
1:05:22well, and then among other things, you
1:05:24see again that like okay, this path now
1:05:26goes from one to one.
1:05:32Okay.
1:05:35And
1:05:36this is actually awesome. This is like
1:05:38superly great structured
1:05:41because it's block diagonal and these
1:05:43blocks are the bucket sizes which are
1:05:46size like root n.
1:05:51So, if you think about the plan, okay,
1:05:54it still doesn't exactly pattern match,
1:05:55but um
1:05:57this A new is like even like much better
1:06:00than this. First of all, there's no rank
1:06:02error at all in A new.
1:06:04And this block structure is um
1:06:07way better. The blocks are of dimension
1:06:09root n.
1:06:11So,
1:06:13uh
1:06:14it's almost like we did too good here
1:06:16because like we we you know we're
1:06:18probably going to need to allow this
1:06:19slack and this slack and we got
1:06:20something that's too good. And you see
1:06:23uh
1:06:23well, we didn't succeed with the rest of
1:06:25this stuff. Like we just kind of made up
1:06:26this matrix A new.
1:06:28And we could strive to maybe like pass a
1:06:33matrix polynomial between A and A new
1:06:36to try to like get this going.
1:06:39But
1:06:40there's only like two points here. This
1:06:42would be like the zero point and this
1:06:43would be like the other point and like
1:06:44that's no good. Like we really needed
1:06:47like to make this matrix polynomial like
1:06:49have as many points involved as we
1:06:51could.
1:06:52So,
1:06:54this doesn't quite work, but it's the
1:06:57right idea.
1:07:03Any questions?
1:07:06Yeah.
1:07:07>> Is there
1:07:08like a
1:07:09yeah, relationship between the format of
1:07:11A new and that of A? I guess what you're
1:07:15trying to say seems to me now that
1:07:17>> [clears throat]
1:07:17>> this kind of like packaging of the
1:07:19bipartite graph is
1:07:22it seems like it's already I guess
1:07:24like making like the matrix I don't know
1:07:27which
1:07:28is like what do you do the result I
1:07:30don't know I guess.
1:07:32>> This
1:07:33is what originally A is not block
1:07:35diagonal it's just block structured. So
1:07:38like there's no reason and like the
1:07:39whole problem is how could you compute
1:07:41the permanent of this fast? You could
1:07:43definitely compute the permanent of this
1:07:44fast but as you say like two to the root
1:07:46n time but like there's not an obvious
1:07:48connection between the permanent of the
1:07:49two of them.
1:07:50I mean they are
1:07:52they're related in this way.
1:07:54Um
1:07:56and maybe you can even a little bit see
1:07:59we kind of want to like get some
1:08:01relationship here
1:08:03and that's where this like J is going to
1:08:05play a role like J is going to somehow
1:08:07again it doesn't quite match up yet but
1:08:08like J is going to kind of match us from
1:08:11like an X type it's going to interpolate
1:08:14between an X type matrix and a matrix
1:08:17that's like more block diagonal than
1:08:19X's.
1:08:21And by cramming all [snorts]
1:08:24something we're almost done by like
1:08:25cramming J's in here instead of X's
1:08:28we're going to
1:08:30uh
1:08:31like make a polynomial interpolation
1:08:32between A and several different
1:08:36reasonably well structured matrices.
1:08:42Okay so we're on to the final idea.
1:08:45Uh
1:08:47let me erase this again.
1:08:49This is truly the last idea. Um
1:08:58So somehow like these buckets are like
1:09:00two course or something so
1:09:03uh
1:09:06we're going to um
1:09:08not number the buckets just one through
1:09:11B anymore
1:09:13or
1:09:14um
1:09:15index the buckets
1:09:22not with numbers one through capital B
1:09:24with
1:09:26strings
1:09:29in
1:09:31sigma to the L.
1:09:34And so, we're just going to name them
1:09:35after strings, not binary strings, but
1:09:37strings over a larger alphabet.
1:09:39And um,
1:09:41when we do this, it's going to be
1:09:43important that the size of the alphabet
1:09:46is bigger than log n for some
1:09:49technical reasons I won't get into. So,
1:09:52we can set it to be like log squared n
1:09:54for safety.
1:09:56Okay, so we need that.
1:09:58And then, we need that the cardinality
1:09:59of this
1:10:01this should have size
1:10:03B, which was square root n or 10 square
1:10:06root n or something.
1:10:08So,
1:10:09this is finally where L comes in.
1:10:13This has to be bigger than log n.
1:10:15And then, the size of this set of
1:10:17strings should be like root n. So, we
1:10:19need what value of L solves this?
1:10:22Um, well, I mean, you need that like L
1:10:24log cardinality of sigma equals log of
1:10:27B.
1:10:29And that solves to
1:10:31uh, L is proportional to
1:10:34log B, which is log n
1:10:36up to constant over log sigma, which is
1:10:38like log log n.
1:10:43Okay, so we're going to name our buckets
1:10:44after strings like this.
1:10:53And um,
1:10:59uh, we're going to repeat the exact same
1:11:01like bucketing that I started with,
1:11:03where I just like, okay, we're going to
1:11:04like
1:11:05bucket
1:11:07buckets of size B, except the buckets
1:11:09are just going to be named with I don't
1:11:12know, this will be named like
1:11:13000 if L is 3, 001,
1:11:17002,
1:11:1900 sigma, whatever. Um, and you know,
1:11:21we're going to have like exactly one
1:11:23edge.
1:11:24Oops, none of these.
1:11:27Um,
1:11:28and we're going to like that little
1:11:30greedy algorithm we're going to
1:11:31do arrange the buckets like this.
1:11:36We're going to add like one more. This
1:11:37is again [laughter] very minor, but like
1:11:38constraint
1:11:40that you know before I said like oh I
1:11:42don't want any buckets to go straight
1:11:44across.
1:11:45Uh I want like no edges
1:11:49in bucket pairs
1:11:56BB' prime. These are not strings unless
1:11:58they have Hamming distance N or L.
1:12:05So actually most typical pairs of
1:12:06strings actually do have maximal Hamming
1:12:08distance, so it's fine.
1:12:14>> [snorts]
1:12:16>> So you know like now like maybe a
1:12:18typical
1:12:20bucket pair
1:12:24Now I'll just illustrate with an L
1:12:26equals three
1:12:27and sigma equals some numbers like
1:12:29digits might be like um I don't know 732
1:12:34{comma} 815. That's in
1:12:37sigma three cross sigma three if we're
1:12:39imagining
1:12:41uh L is three and sigma is at least you
1:12:44know the number of digits.
1:12:48Okay, so [snorts] like you know down
1:12:49here we might have like 732 and like 815
1:12:53and then there's some
1:12:55edge between them and indeed these two
1:12:56strings have Hamming distance three, so
1:12:57it's okay.
1:13:00Um
1:13:01Okay.
1:13:03We're almost done genuinely. Hang in
1:13:04there. Um
1:13:06So
1:13:07before you have like to make this work
1:13:09it was like mildly important that
1:13:12you know we picked a nice ordering for
1:13:13the bucket pairs. These These were named
1:13:15by bucket pairs, right? So we did one
1:13:16two and then it's reverse two one and
1:13:18then we did one three and then it's
1:13:19reverse three one.
1:13:20>> [snorts]
1:13:20>> So the bucket pairs were like naturally
1:13:21grouped into pairs of size two
1:13:24and we put like X's on the pairs.
1:13:27Okay?
1:13:28Now our you know our bucket pairs look
1:13:30like this.
1:13:32And I claim these
1:13:34can naturally get grouped up
1:13:36into groups of cardinality two to the L.
1:13:41So, [snorts]
1:13:42um
1:13:43it's going to be kind of a picture here
1:13:44where like we'll get like a group of
1:13:45size two to the L or index by zero one
1:13:48to the L here
1:13:49and zero one to the L here and also here
1:13:52and also here.
1:13:53And like instead of enforcing that like
1:13:55these plain X's go across, we're going
1:13:57to enforce that literally this script X
1:13:59goes across.
1:14:01And
1:14:02it's not super important, but like how
1:14:04is this grouped up?
1:14:06Uh this particular one would go into the
1:14:08group
1:14:10whose group name
1:14:12is um
1:14:15uh
1:14:17seven and eight,
1:14:19one and three,
1:14:21and like two and five.
1:14:25So, what's going on here?
1:14:28I would like to group together all
1:14:29bucket pairs into a let's say a group
1:14:31like this. This means that in the two
1:14:33bucket pair names, uh the first
1:14:36coordinates have seven and eight in some
1:14:38order. The second coordinates have one
1:14:39and three in some order. And the third
1:14:41coordinates have two and five in some
1:14:42order.
1:14:44And then within this group
1:14:51you can like pin down
1:14:55like a particular bucket pair
1:15:00using
1:15:02some string like U in zero one to the L.
1:15:08>> [snorts]
1:15:08>> Informally like inside this group, if I
1:15:10give you like, I don't know, U equals
1:15:13zero one zero, say,
1:15:15the convention is that means like okay,
1:15:17the the left
1:15:19string should have the smaller of the
1:15:21two digits if it's zero. And one means
1:15:24like the the left string here should
1:15:26have the larger of the two digits. And
1:15:28like the this one being zero like the
1:15:30third bit or third symbol should be uh
1:15:33smaller, the last one should be the
1:15:34smaller of the two.
1:15:36Okay, I mean that's actually not very
1:15:37important, but just within this group,
1:15:39you get like two to the L
1:15:41bucket pairs that look like this, and
1:15:43they're naturally indexed by binary
1:15:45strings.
1:15:48Okay, so
1:15:54um
1:15:58So, the point is we do the exact same
1:16:01thing as before, except now like our
1:16:04inside vertices have like different
1:16:05names,
1:16:06and they're naturally like grouped into
1:16:08groups that are
1:16:10indexed by 0 1 to the L.
1:16:20And before, you know, we were like, "Oh,
1:16:22the most natural thing would just be to
1:16:23put the identity matrix here and have it
1:16:25go across."
1:16:26Instead, because to make this all work,
1:16:28we're really going to be like, "No, no,
1:16:29no, we're going to put in
1:16:31the
1:16:33bipartite graph corresponding to this
1:16:34special script X matrix, which is really
1:16:36like this anti-diagonal matrix that like
1:16:38goes
1:16:39goes that it's like this.
1:16:45Okay, this is like script X. Like a bit
1:16:47string here is connected to its
1:16:50bitwise negation.
1:16:52Okay? But, it's fine. You can always
1:16:54rearrange the right-hand side
1:16:55appropriately because these are just
1:16:57This is like a matching, so you just
1:16:59you just reshuffle things around.
1:17:02So, what I'm saying is you can arrange
1:17:04that A looks like L times
1:17:09diag script X script X
1:17:12{dot} {dot} {dot} script X.
1:17:15And this is like a little bit different
1:17:16here. This middle matrix,
1:17:19you know, used to be these like two by
1:17:20two X's down the diagonal.
1:17:22Now, it's like
1:17:25these like a two to the L by two to the
1:17:27L X's down the diagonal. But, okay.
1:17:33Okay.
1:17:35Uh
1:17:37Okay.
1:17:39And naturally, uh we're going to be like
1:17:41jamming uh JIs in the in place of these
1:17:45script axes.
1:17:48So,
1:17:49uh
1:17:50Sorry.
1:17:51Um
1:18:00>> [clears throat]
1:18:00>> Okay, so now remember we did before this
1:18:02like thought experiment where we had the
1:18:03little axes and I was like, "Oh, what
1:18:05happens if you change them to straight
1:18:06across eyes?" Oh, then the new thing
1:18:10would be
1:18:13block diagonal.
1:18:14So, it's similar here and I call this an
1:18:16exercise. Um
1:18:18if you have some matrix
1:18:22X hat I
1:18:24and it's
1:18:26I's coordinate BLOCK DIAGONAL.
1:18:34THEN, UH FOR SOME I
1:18:37then if you form A L times diag of this
1:18:41thing
1:18:42where you change them all to X hat I's
1:18:48then uh
1:18:49you don't get this like glorious block
1:18:51diagonal matrix with blocks of size root
1:18:53N, but it's still good. Um this IS BLOCK
1:18:57DIAGONAL
1:18:58>> [applause]
1:19:01>> WITH BLOCKS
1:19:04of dimension
1:19:07at most
1:19:08N over size of your alphabet.
1:19:11Cuz somehow you get like
1:19:13like only you kind of like only uncross
1:19:15one coordinate.
1:19:17And so, you don't get like the full
1:19:18savings, but you get like savings equal
1:19:20to like the size of the alphabet.
1:19:22Then you have to take that as a uh a
1:19:25little exercise. But that's great
1:19:27because we set up the alphabet to be
1:19:28like, okay, like a little bit bigger
1:19:29than log N. So, this is still fine
1:19:32for this point of view.
1:19:34Cuz it's block diagonal with blocks of
1:19:35dimension N over poly log N.
1:19:39Okay. So, now we are
1:19:42uh
1:19:43done.
1:19:44Uh so, to complete the plan,
1:19:47this plan here,
1:19:49>> [applause]
1:19:55>> UH WE JUST DEFINE
1:19:58A SUB OF T to be L times diag
1:20:05like J T J T
1:20:10J T
1:20:11>> [applause]
1:20:12>> times R prime
1:20:14like down here.
1:20:16And we did it. So, it's a matrix
1:20:19polynomial.
1:20:20Uh its degree is the same as the degree
1:20:23of J, which is this D.
1:20:26And if you plug in zero for T
1:20:30here, then all these script J's become
1:20:33script X's and we get the exact uh
1:20:35factorization of A.
1:20:38And finally, for T being uh or I being
1:20:41one through L,
1:20:42uh
1:20:43for any I like that, if you plug it in
1:20:45here, you'll get like an X hat I, which
1:20:47is
1:20:48um
1:20:50I'th coordinate block diagonal plus low
1:20:52rank.
1:20:54So, [snorts] this thing will become like
1:20:57L times diag
1:21:00of like
1:21:01I'th coordinate block diagonal
1:21:04plus low rank.
1:21:07And like many copies of that.
1:21:10Okay, and it's linear, so you can pull
1:21:11out this piece and the L times the block
1:21:13diagonal times R prime
1:21:16is block diagonal with blocks of
1:21:17dimension at most n over poly-log-n.
1:21:19And then the L times low rank times R
1:21:22prime things,
1:21:23uh they stay low rank and it it stacks
1:21:25up. So, like this
1:21:30each piece has like fractional rank at
1:21:31most
1:21:33L to the 100, 1 over L to the 100.
1:21:38So, the overall rank of the diagonalized
1:21:40version of this low rank thing
1:21:42>> [snorts and clears throat]
1:21:42>> uh is overall fractional rank 1 over L
1:21:44to the 100 and L is like log n, so you
1:21:47get fractional rank like n over
1:21:50log to the 100 basically.
1:21:53And that's it.
1:21:55Okay, so we'll get back to regularly
1:21:56scheduled programming next time.

About this transcript

This page contains the full transcript of ETH False II: completing the proof by Ryan O'Donnell, generated from the public captions YouTube serves with the video. The transcript has 11,374 words across 2,111 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.