So welcome to the workshop. We're really happy with such great attendance on expansion complexity and lifting theorems Really happy to have our professor Arquitif Chattopadhyaya here for the first talk I've known Arquitif for a long time He goes PhD in McGill and I heard of him because he solved the problem that I was really interested in which is To prove a lower bound for set disjointness in the multi-party number on forehead model Which was a really great result So I got to know him a long time ago from that and then he did a postdoc in Toronto, and he's been at TFIR for Seven years. He's a number of remarkable results in communication complexity and circuit complexity, and he's also great speakers. So Without further ado Thank You Tony for the kind introduction so My idea for asking the organizers to Organize a workshop on extension complexity and lifting theorem was to learn about extension complexity and lifting theorem Because I really don't know anything about it about extension complexity and their gift back to me was that I am the first speaker So you'll have to bear with me with whatever little I know. I only know a little bit about lifting theorems Thanks to a bunch of very smart students that I had But yeah, I mean most of this is classical stuff a lot of stuff has happened and I mean, I think several speakers will follow me up and Tell you more about them and more about those those very interesting work So I will assume some familiarity with communication complexity, okay, so I Will quickly recall so Alice and Bob. Oh By the way, the thing that I'm going to since there is no space for Writing on the whiteboard. This is based on joint work with Mihal Kautsky Bruno Lough and Shagnik Mukhapadhyay also a very recent work with You are filmers Sajin Korot, Urma and Tony So we will see two styles of lifting theorems but first let me Talk about the basic setup. So there's Alice and she gets x Bob gets y as you all know and Then they start communicating according to some Predetermined protocol they have to compute some function f Which could be a partial function or a or even a search problem? okay, but I will assume it to be function for now and And I will assume that you know for simplicity. Let's just assume that they talk one a bit at a time So there are rounds in each round the protocol specifies Who's to talk and if Alice is to talk Alice sends one bit based on what she sees on her side So it's some arbitrary function Okay, and this is something that you all of you know. Okay, so at the end of the earth's round They output the answer Okay, so the protocol which I will call pi pi of x y should be exactly equal to f of x y This is the goal Okay, and now there's another model which is even more elementary in which case you have some input which I will call Z So this is the first bit of z and this is the nth bit of z and you have some other function. Let's say h of 01 to the and in this model which is the query model You have a decision tree. So it's a pro it's it's an some algorithm Which queries a particular bit of z at the root maybe it queries the z1 then it queries the second If this is zero this it goes this way and then maybe it queries the 17th bit and so on and then at the leaves they are labeled either zero or one or Whatever the range of the function is Because this may be also again a partial function or a search problem and so for every possible input Alice this this query algorithm There is a fixed path because I'm assuming deterministic. There's a fixed path that gets traveled Quaring each bit at a time and you reach a leaf and then you output whatever the leaf has labeled, right? So this looks like a really really simple model where you know, there is no Alice no Bob and The algorithm doesn't get to see Any input bit for every bit that it wants to see it has to pay a cost of one unit, okay? So so that's the setup and What we are going to do today and what lifting theorems the kind of lift if lifting theorems that we will talk about is that sort Of a very interesting connection between you know hardness if a function is hard in this model It means meaning that you have to in the worst case query a lot of bits before you can give the answer then Associated or related function becomes hard in this very different looking model called communication model Okay, this is the goal of lifting theorem. So here's an example Which all of you know now here, of course you you're given two sets x and y and what you have to output is Is one if and only if you know x Intersection y is the empty set Okay, so you can think of them as the characteristic vector of two sets And you want to find out if the two sets are disjoint only then you want to output one Here on the other hand and the query model. Let's look at this function or Okay, very simple function. Yeah, so this or of z is equal to one if and only if there exists an I So that z i is equal to one Okay, now this is something of course you have you know seen many times But if you think about it Somehow the hardness of set disjoint is a very hard function in the communication complexity model The hardness is associated with this fact that what can Alice and Bob do because you know, they've got this Alice has got x and Bob has got y now what they want to find out is Basically if there is an x i and y i says that x i y i if there is an i says that x i and y i are both One right so in some sense the function can be rewritten as You sort of do first bitwise and of x and y you get an n-bit string and then you want to find out whether there is a One in that n-bit string So although Alice has full access to x and Bob has full access to y the relevant information seems to be in the String if I may call it z which is equal to the bitwise. This is the bitwise and of x and y Right and just looking at x and y they have very little information about this z Okay, if x i is zero then of course at that position x i and y i cannot be one But then Bob doesn't know that right so the so the inform a they seem to be almost Information wise as much blinded as a query algorithm is when the query algorithm doesn't get any access to z Right, so they have to find out for each bit and it seems that to find out for each bit Alice has to tell Bob Look, I've got here a one. What have you got there? Okay, so this is of course a very very vague idea because We will see a counter example very soon about this that this of course doesn't happen always Okay, this happens only Only in some special situations turns out for said disjointed this can be formalized and that's the formal proof That indeed because the query complexity of or so we know that and this is the notation I will use the query complexity of or this is deterministic decision tree query complexity of or is equal to n This is of course informal Yeah, this implies that the Is also equal to omega n okay, and lifting theorems would try to make this form Okay, so And in let me also remind you that in communication complexity Many functions that we deal with like said disjoin this inner product all of these can be thought of as First Alice and Bob have to do a bit wise certain operation, and then they have to compute some other function. So for example You know Said disjoin us is can be written as or of and or nor of and right inner product can be written as x or of and and So I'm just reminding you If you think about it most commonly used functions have this kind of composition property, and it's something to do with the Incompatibility of the outer function and the inner function that makes the problem almost as hard as the decision tree version for the outer function okay but So what I'm trying to say is that one may expect that the decision tree complexity Reflects in the communication complexity and another reason why you should think of that? This is very natural is suppose in general. I were to give you some function capital F Which is F composed with so this is a general setup F composed with G okay, and One natural communication strategy for computing F would be to look at the decision tree of F Okay, so F is some function from Z to 0 1 and G is some gadget Okay, so each bit of Z is being hidden. Yeah, it's being distributed or imported by G Okay, so a natural communication strategy for for for capital F is to look at the decision tree Protocol for small F and whenever and this was something Tony was saying yesterday Whenever you know say here I want to find out what is Z1 Well, I can't find out what is Z1 for that. I need to do the first instance of G X1 Y1 If I evaluate that then I get Z1 Okay, and I will employ the best communication protocol that I have for G Okay, and use that to evaluate Z1 and then I know Z1 and Alice and Bob would now at this point Both knows that one and maybe Z1 maybe this evaluation gives me one So I go to the right side and now this was maybe Z5 now. I evaluate G X5 Y5 Yeah, so this is the fifth block and the of X and Y and then this will give me Z5 And then again knowing that Alice and Bob can continue with Simulating this decision tree. Okay, and if you do that then this strategy Shows that the deterministic communication complexity of F is at most the decision tree complexity of small F times the communication complexity of G Okay, the question is is this optimal the set this join as example or inner product suggests Well, yeah, this probably is optimal, but this is not always the case here are two Examples that I would like to come back sort of counter examples that I would like to come back Later also at the end of the talk because this will lead us to a very interesting subject. I think so Trivial pathological looking example. Suppose I take XOR of XOR Okay, now XOR which is the parity function of course has very large deterministic communication Query complexity until and unless you know all the bits. You have no idea about XOR so you have to query everything and get and only then would you be able to know the answer right and the come so You know if I look at XOR of XOR I Would expect that the that the communication complex if such a theorem was true always then I would have expected That the deterministic communication complexity of this function would have been very large But of course, this is not true because XOR of XOR Squishes into XOR and so Alice can just Take the XOR of her bits and send it over in one bit to Bob and then Bob can just evaluate the answer So this looks like a pathological example. So some some care has to go into this Okay, you can't of course say that this is always true Okay, this looks like okay. This can be easily avoided. So now one important thing is we would also like to assume as I said my Function the outer function f I want to assume as little about it as possible For instance, it may not be a Total function. It could be a partial function In fact the lifting theorems are often used in the context when the outer function is a partial function or a search problem So here's another example suppose you know, I say that f is a function which is The input to f sorry input of f. So my promise Is the following Either Every zi is equal to zero or there exists a unique I such that zi equals one so I Have an n-bit string and I'm giving you the promise that either all of them is zero What there's exactly one the hamming weight is one and you have to distinguish these two cases Now if you go to the query model, this is the hard instance of the or function, right? This is this is the one on which you will spend most of your time because you will keep querying for a one You will never get it until the adversary and when he has exhausted you he will show you the one Or he may not show you the one, right? So this is very hard. This takes n bits Okay, so this is going to be the communication complexity. So this is let's say promise star The decision tree complexity of promise star is still omega n right now, let's look at F which is promise star of equality now equality I equality is just another important function equality is And of Exor So equality is a classical example of a hard function in deterministic communication complexity and What you would like to Think that this function Because you have composed it with a hard function here this function should have very large communication complexity in particular suppose I had Instances so let me write it here. This is an instance of equality and this is m each equality string is an m bit string This maybe I should write it larger right So you would you you you think that this should take n times m bits of communication Because this by the naive protocol whenever you would like to evaluate over here You have to spend m bits and I showed you a convinced you that this the decision tree complexity of the promised or is Is very large right, but it turns out It's a cute exercise to show that you know the The communication complexity of this f no matter how large is n is actually order m Okay, because of this promise Okay, so When you Yeah, exactly. Yeah, I mean it's promised in the sense that you can assume that they are free to answer whenever the promise is broken They can answer anything. Yeah, just as in this case. I gave you the promise if the z is were different You could answer anything right despite that despite knowing that it was the hardest possible Thing so you would have you could have hoped this now this requires a bit more thought it's not it's not hard I mean, you know, okay, I'll leave it with a curious interesting exercise So the point is you know what I'm trying to say is that not every gadget Is is is useful in rendering the communication model to the query model? Yeah, meaning or or you have to be very careful about this Okay, so you can't you can't hope that you know in every situation this would have Okay, and it's it's This particular one I would like you to work it out because you will see that the that the fact that the communication Sort of model has this side information. Yeah in the sense that okay, there's some core. I mean there's correlation things are correlated Okay, I mean it is not independent and Alice and Bob are able to see all of x and all of y that side information can be used in situations to bypass the following the knife following the knife algorithm So now let me try to say the main theorems So in some sense these theorems are rather delicate about I Mean, it's amazing that they work when they work that they work so very generally Yeah, yeah, so one of the theorems will show. Yeah, okay delicate in the sense Okay, one of the theorems will show that if you picked a large enough random gadget this will work Okay, so Regardless of what the other functions Okay, so I want to give you two theorems as I said From these two works one this will generalize a Series of works first by Raz and Mackenzie back in the early 90s and then Tony with Mika Gus and Tom Watson's yes So for this promised or composed with this equality. Yes, if M is equal to one Yes, then in that case this just becomes this said disjointness problem Equality is an XOR and that makes a huge difference. Oh Said disjointness was an and Right. So what I was saying was that this is generalization of Raz and Mackenzie And I think Raz and Mackenzie were the first ones to prove a lifting theorem of the kind That we are that we'll talk about but I mean as a Disclaimer, I want to say that there are many instances of lifting theorems depends on what you are lifting to what? Okay, so there are lifting theorems which which are more algebraic in nature very important example of this is Sherstoff's lifting theorem independently also discovered by she and zoo where he showed that you know a different measure of One-party functions like approximate degree Can be lifted into randomized communication complexity? Okay, we are not talking about such lifting theorems the lifting theorems that we will talk about are when you want to lift lift Specifically the decision tree complexity measure So in order to state our lifting theorem I want to tell you about two other notions that will be useful one of which you might have already seen so How do you prove lower bounds against communication? Protocols the basic building blocks. I'm sure all of you know of a communication protocol is that R-R-R rectangles So in other words if I have a communication protocol of cost C then the communication matrix Which is? This matrix One associated with all possible inputs of Alice the other associated with all possible inputs of Bob and this is a Boolean matrix You know so each entry here is the value of f If this is x, this is why this is x y Right So that's the communication matrix and this communication matrix is broken into two to the C Monochromatic sub matrices by a communication protocol a communication protocol just you know takes a certain cut here as Alice speaks she divides her input onto two parts then Bob speaks Bob divides his input onto two parts And if you do this you will see that it gets broken up into chunks and each of this chunk At the end at the leaf each leaf represents a Submatrix and these submatrix have to be monochromatic Because if I assume a deterministic protocol then you know that there's no no no no possibility of error So it basically breaks down this communication matrix into two to the C at most to the C monochromatic sub matrices okay, and these sub matrices are what I will call combinatorial rectangles and One way to prove lower bound against communication complexity Communication protocols is to say well you're going to break it down into two to the C Monochromatic Submatrices then at least one of them the average size of that such a sub matrix is two to the minus C the fractional size right and You if you show that there cannot be a monochromatic rectangle of size fractional size to the minus C Then you are done right then then then you cannot have C bits so now I'm going to talk about a property of of this so We are in this situation F is F composed with G And I'm going to talk a property of this gadget G because I want to prove a lifting theorem meaning, you know Some property of G will ensure that no matter what F is the decision sees a goal is to say What property of G? ensures That the knife protocol is a simple protocol right so DCC of F is equal to Yeah, we saw that this is all not always true right I gave you two examples What we want to find out is what is that a sufficient property of G that? ensures that this holds Okay, and more generally Since I don't have time let me also say the same thing should hold for randomized communication So there's a difference between epsilon and epsilon prime. This is technical stuff So yeah, so you want these things to be true. Okay, so it's all about G There is because it's G's somehow encoding this in such a way that as I said even though you have access to Massive amounts of side side information even under promises of weird correlations. Yeah, it doesn't matter G is so hard that Alice and Bob are basically forced to follow this knife strategy of querying bit by bit Okay, so we want to find out an interesting Properties of G that that is sufficient for for such purposes okay, so In order to talk about those properties of G. I will have to talk about this properties about rectangles So I want to talk about two things one is as the title of my talk Said one is hitting distributions They seem quite different and the other is discrepancy so Now what hitting distribution says is that you know so I look at G I look at all the monochromatic rectangles of G now there are two kinds of monochromatic rectangles of G Yeah So my question is in the composition G like The examples you gave G is a very low arity function, right? Maybe just on one bit The low the lower the better for applications. Yes, that's true And we also assume that so each copy of G would act on like disjoint set of areas. Yes. Yes This is block composition. Yeah This notation somehow traditionally this was you so this block. There's no overlap. Yeah, that's very important Okay, so there are there. I mean I will talk about a C monochromatic Rectangle of G this should be clear C is some C is in zero one, right? So it's either zero monochromatic rectangles of G or one monochromatic rectangles of G now I Want to say that not only G is hard in the sense that it has no small monochromatic rectangles, but The so That's true of a random function a random function will not have large monochromatic rectangles Okay, but now I want to say something which is which is not true of a random function It's okay at one point in one since it has no large monochromatic rectangles That's like a random function, but you know this at the same time it has It has not too large monochromatic rectangles. It has somewhat large monochromatic rectangles and this somewhat large monochromatic rectangles are sort of nicely distributed And what do I mean by that? formally I have a distribution for each C hitting distribution that I will say sigma C which samples Okay, which samples a C monochromatic rectangle at random. So this is some distribution, okay, and Under this sampling if you give me in this matrix any larger rectangle This is some large rectangle not necessarily monochromatic, of course It is so some large rectangle the probability when you sample according to sigma C a C monochromatic rectangle This rectangle is R R intersects with your sampled rectangle Let's say u cross v Yeah, this is very small Sorry intersects. Oh, this is large. Yeah, okay So what do I mean by large? So there are two parameters here the probability must be the probability of not intersecting is very small like delta and the largeness of R the size of R so R is Greater than equal to 2 to the minus h large. So I'm always talking about fractional fractional largeness, okay So I want to have these distributions So no matter which rectangle you give me if I have two distributions Sigma C that is Sigma 0 and Sigma 1 you want to hit with a zero monochromatic rectangle I'll sample from Sigma 0 and then you know, I will If I sample such a rectangle u cross v according to my distribution Sigma 0 then very likely I'm going to hit This you're given rectangle Okay, and I can do that also with Sigma 1 in particular therefore that means that your large rectangle is not monochromatic because I've been able to hit it with non-zero probability with Very large probability both by a zero monochromatic rectangle and a one monochromatic rectangle So in particular your your rectangle is not it cannot be monochromatic The the the simple condition that we talked about before but you see you need to have these things These are not satisfied by a random gadget. It's very delicate distribution.  I mean who knows what it what it for all R for all R Sorry for all R. Yeah, u cross v is being sampled u cross v is being sampled according to Sigma 6 u v is sampled according to Sigma 6 so when this happens I say that G So this is said G has the Delta H Property seems like barely I will have the time to state the two theorems. Okay, so the first theorem is the following that Okay, I'm again stating this informally because yeah, you can check out the paper and look at it more carefully so assume that So you're looking at f n composed with G B Yeah, so the so the so the block size of G is b bits and you have n instances of G and you're creating this function and Let's assume that one is less than it. Okay. This is an important Epsilon is some some fixed Number between 0 and 1 and G has the heating Delta H heating property then I can show I'm intentionally writing it in this way Because this will suggest how the proof goes so Yeah, so what this means is if you give me a communication protocol of This much cost for this protocol then I will be able to extract a decision tree So that's how the proof goes you've given me an arbitrary protocol, which is working in weird ways We have no idea But using the fact that G has this heating distributions. I will be able to extract a Decision tree for f with cost this much and the important thing is, you know, this cost is being is being Slashed by this this age Yesterday you had a question about why should this saving take place? Well, the intuition is very clear. Why should the saving happen? Yeah, because G is H hard. Okay, so until and unless you have communicated sort of age bits Okay, so so, you know, you have here the inputs of Alice and Bob Yeah, not this. I mean in order to so you you are evaluating G on each of these blocks, right? And this the the individual instance of G is you should assume it's H hard You require this shows clearly that this heating distribution a trivial corollary of the heating distribution Is that the communication complexity of G is H? Okay, so until and unless you spend H bits on a focused coordinate You know nothing about it. This is something you have to prove, but I'm saying this is the intuition, right? So every what H bits worth of communication you are revealing perhaps too much about one bit at that point Aha, you know the one of the one of the coordinates has become very clear, right and so on Average You know this is happening. Okay, so this is this is the intuition to expect. This is very clear. Okay, but you have to formalize this Okay, so that's that's theorem one and Yes, yes for all epsilon Yeah, and delta we assume is less than one over hundred whenever delta is one over hundred this will work for all epsilon in Epsilon is any any parameter No epsilon does not depend on ends. Oh epsilon in principle could So epsilon is between let's say now for now epsilon is a fixed number between zero and one and Whenever delta is less than one over hundred this inequality is satisfied Okay, so that's the first theorem The second theorem is Yes So if g was chosen to be a random function, right the thing that's unclear is if whether a random function satisfies the heating distribution No, it's the random function will not satisfy. Yeah, you can prove that a random function with high probability will not satisfy This theorem does not imply that no for a random function No And now I'm going to state the theorem with Tony and others where where we will be able to show that a random function works The only the okay, let me state the other theorem and then I'll say the the the way these things compare For which this works, uh, there are many Examples, uh, although a random function doesn't satisfy it But the examples that but many of the cardinal problems and communication complexity in this regard do not behave like random function for example the index indexing function the inner product function the gap hamming problem All of these would satisfy this, okay And so, you know Okay, let me first state the theorem for the other thing. So what is discrepancy? Okay I mean if you have taken a course in communication complexity of surely seen this but let me still state it again Okay discrepancy is so here so far Uh discrepancy in some sense will seem like an overkill. Okay, but it's very powerful So if you have a communication protocol it Basically, uh, we all know it partitions the communication matrix into 2 to the c More completely monochromatic rectangles, right now it turns out now suppose I say that I have forget that not only My function is hard in the sense that not only does it not have non large monochromatic rectangles If your rectangle is slightly large It has very small discrepancy meaning, you know, if you think of it as being points are being colored by 2 colors 0 and 1 The coloring has very small discrepancy Okay, in the sense that they're roughly balanced either your your your rectangle is extremely small Or they're roughly balanced. Okay, so, uh, formally you would want to say that the discrepancy Of a rectangle are For a function f is exactly equal to the probability Is this clear so so you're looking at Yeah, so x y is chosen under the uniform distribution So for now in this talk, I will only deal with the uniform distribution. Okay, so you sample So basically you want you you've given some rectangle Okay, and you randomly choose an x y and what's the probability? So it's basically, you know, the the probability mass of The ones inside this Minus the probability mass of the zeros inside is the difference of these two probability masses It's a very natural way to measure, you know, if you had a monochromatic rectangle Then this discrepancy would just be the probability mass of this rectangle Right because yeah everything is one colored the same way And now you're looking at the difference of these two masses Okay, and if they had perfect, uh, balanced coloring then this would become zero Right, so the smaller this difference is The less biased this rectangle is and therefore this is Being even further from being monochromatic Okay, so it turns out That this is a very powerful quantity If you worked on extractors, this is this may this may This may remind you of an of an extractor like property Because I'm using that word because I talked about hitting distributions there. This is somewhat similar to an extractor But when you have this very powerful property, then you can in fact show that not only so maybe we should say g here because we are talking about g Yeah, so so not only is g hard for deterministic protocols. It's even hard for randomized protocols Okay, and our theorem 2 is now saying And and oh the important remark is if you choose a random function g on b bits So it's it's a fact that you know For a random g The discrepancy sorry, this is discrepancy of a rectangle and the discrepancy is The maximization of this quantity over all possible rectangles Okay, so discrepancy of discrepancy of g Is maximize this same quantity r Over all possible rectangles now for a random g discrepancy of g Is extremely small is is like about 2 to the minus I'm assuming g is over b bits Okay, so for a random g is extremely small exponentially small okay That's the nice thing. So most g's will have this property that will have a small discrepancy and the theorem 2 with With uh, you are Sajin or and Tony Is the following result again Informally because I think I'm running out of time is that same setup now f is f n of Gb, okay, and Let's say The discrepancy of g Is Is is is at most 2 to the minus eta b for some constant eta Okay And b Is at least c times log n Where c is some constant that depends on eta Okay, then we can say two things Okay, so we make we made a stronger assumption and we are able to prove much stronger things, which is that not only now The the the deterministic query hardness lifts to the hardness for deterministic protocols But also as you can expect the randomized hardness Lifts the randomized decision tree hardness lifts to the randomized communication hardness Okay So the advantage of this theorem is that as I said Is that it applies to yeah random gadgets g and you also get a randomized lower bound, right? Such a randomized lower bound. We don't know how to obtain using Hitting distribution property, okay, or any any any any let's say, uh, natural generalization of hitting distribution property Okay Sorry in place of b. Yes. Yes. Yes. Yes Because the communication complexity of of g would be about log 1 over discrepancy of g Okay, so let me now just try to say a few very Brief things about how the proofs go, okay So The point is in each of this In both these theorems what you would start with is some arbitrary communication protocol I will stick for now with the deterministic protocol Okay, so you're given some deterministic protocol And you want to extract a decision tree out of this deterministic protocol With absolutely no idea how the internals of the protocol is working, right? But if you think about a protocol a protocol itself is also a tree, right? You have alice Who talks then you have bob And then again alice And so on Right and here the leaves represent as I said Rectangles, okay, I'm talking about deterministic protocols Okay now The point is alice of course is no longer in this protocol Quaring one bit. She's computing an arbitrary function on his on her side And so is bob, right and we want to extract from here Another decision tree. This is some sort of a tree and we want to extract another decision tree where you will be for We'll be just querying One bit at a time So the idea is So I want to construct this decision tree and the decision tree. What is the input the input is Some z in 0 1 to the n right so the point is the general Strategy would be to delay querying a bit Okay, there will be some events that will trigger me to In the query in the in the query protocol to to to make a query And when does that happen at the beginning things are nice because you know the protocol has not said anything So, you know all possible inputs for now if you were just watching The transcript of this protocol how which path is this executing in the protocol tree at the very beginning It could be you know nothing you it could be the whole set of inputs, right? Then you know alice compute some function and maybe you know, this is one So you go down this path when you go down this path Some information about alice's side is leaked, right? And if alices Revealed too much information about a particular bit Then that's a cause of alarm because you know alice's input might start looking like fixed getting fixed in that particular coordinate right, so the idea is that you want to sort of Keep a measure about each coordinate, okay And as long as it's some sort of a measure complexity measure and as long as that measure is large You want to say well that bit that particular coordinate is far from being revealed Okay, in the two theorems we use two different measures and when that measure is low on a particular coordinate Then you will make a query and if you make a query Again the intuition is is is clear. Why did the measure go? Why did the measure becomes low on that particular coordinate because alice and bob chose to communicate Something specific about that coordinate if they have done so Then you then then the natural expectation is Well, they've only communicated c bits and most of these c bits were talking about this coordinate Then the other coordinates if once I query about this and project myself onto the other coordinates Very little must be known about these other coordinates each time I make a query I must While alice and bob chose to make the this particular coordinate. I'm saying it in a very vague way Alice and bob chose to Reveal a lot about this coordinate You know, so this coordinate became very very Fixed looking like the other coordinates Remained unfixed. So when I project I should gain back something. This is the this is the rough idea okay, and in the case of The second theorem this measure is about this measure That that captures this this intuition is the following. It's it's a mini entropy based measure So what you want to say is if you have two random variables x and y right In fact, just let's first talk about One random variable you have a random variable x and so x is Formed of x 1 to x n right each xi Let's say is in 0 1 to the b yeah, so We want to talk about the density Of x Now what is the density of x the density of x if it is It is equal to let's say gamma then what I want is that For all subsets of n Right, so this is the some subset of coordinates that I chose to pick Yeah the min entropy Of x projected down to that sub Those those those set of sub those set of coordinates right. This is just a projection of x right that well if things were perfect this min entropy would be equal to i times the cardinality of i times b that's the maximum maximum possible entropy that you could have Well, you wouldn't have that but you would have that at least gamma times the size of i times b so i times b is the maximum possible min entropy because you're you know, you're yeah You're over b bits that i coordinates But you want to have at least a certain fraction of that and this is true for every possible subset i So then I say that the density of the random variable x is x is gamma yes, why isn't x I just uniformly distributed because you are just No x is not uniformly distributed x is a random variable I have not assumed that x is uniformly distributed or anything x is not uniformly distributed Okay, and similarly I could define y Arbitrally distributed, but the point is x and y are independent because I'm in a rectangle Okay, so so I could define that and at each Roughly very very roughly at each node of the protocol tree The invariant that I I want to keep an invariant that will preserve this this uncertainty about the coordinates is that the min entropy of both x and y Sorry, the density of both x and y measured in terms of min entropy is large Okay, these two properties discrepancy and the deltas property. Mm-hmm discrepancy is strictly stronger than the deltas property. They're they're not comparable They're incomparable one doesn't imply the other As country because you said like we have a stronger assumption here They're free able to prove a stronger result, but there's not strictly a stronger assumption. No, no, no Yeah, no, it's not a stronger result in the sense that okay. We can prove the same result here, but we can prove additionally Uh result about randomized lifting. I said it's stronger in that sense Yeah, but the properties seem incomparable Why is it uh the case like like you said a random function has high discrepancy, right? Has small discrepancy. Yeah, just No, but then why does that kind of not seem to imply like maybe with like a for a weak Like parameters delta h that it it it should have delta h property Like there it depends on what I said delta to be right You want the the rectangles Uh, you know to be to be well spread out the monochromatic rectangles, right? And if you're given a sort of a large rectangle, yeah, uh, then If you think about it if you if your rectangle the monochromatic rectangles are not too large In size not sufficiently large in size then you have no chance of catching a largeish rectangle Okay for in order to have this Distributional thing You you you if you think you will see that you need to have Rectangles of a sufficiently large size and a random and a random g does not permit that So that is why you can't have these things nicely spread out


Anybody that calls himself a 10. So that's what we look like. I've gotten people say that I was sterling shepherd. I mean, just because the stash people said Tom Selleck, but I don't know. I don't know. Syndrome from the Incredibles. I actually dressed up as Tim for Halloween one day. Nobody. My powers. Drake. Trevino yesterday. He told me I looked like a picture hob when I was like, no shot. Look at that. I haven't dealt with it a lot. I get that one a lot too. Yeah. Those are the two. I've gotten a few before, but none that I've done. Like, I have a lot to show. Peaky blinders. I don't know. I'm not good with celebrities. Actually, hot take. Lou Trevino says Billy Butcher from The Boys. I don't see it, but that's what he says. And he's pushing it hard. So don't let him say that. Or you can't ask him about it. But other than that.


Hello and welcome to the session. My name is Mansi and I am going to help you with the following question. The question says, the front compound wall of a house is decorated by wooden spheres of diameter 21 cm. Placed on small supports are shown in figure. Eight such spheres are used for this purpose and are to be painted silver. Each support is a cylinder of radius 1.5 cm and height 7 cm and is to be painted black. Find the cost of paint required if silver paint cost 25 paisa per cm square and black paint cost 5 paisa per cm square. So this is figure given to us in the question. Let us start with a solution to this question. Clearly we have to subtract the part of the sphere that is resting on the sphere while calculating the cost of silver paint. First of all we see that surface area r square minus equal to 21 by 2 r is equal to 1.5 cm. So something like this is in the question that the diameter is 21 cm so radius will be 21 by 2 cm and also it is given that each support is on a cylinder of radius 1.5 cm that is resting will have a radius of 1.5 cm and so small r becomes 1.5 cm and capital r is 21 by 2 cm. So we simply put in the values here and we get 1 by 4 because square of 21 is 441 minus minus 2.25 is 438 paisa that means for 1 cm square it is 25 paisa 5 by 100. Now we divide this by 100 to calculate this we get h where r is the radius of the cylinder and height of the cylinder that is equal to 8 into 2 into 22 by 7 into 1.5 that is the radius into 7 that is the height. That is equal to 5 cm square in the terms of rupees it will be 26.40. Therefore we can say that the question and enjoyed the session. Have a good day.


good afternoon everybody how's everybody doing? So um how many people know what this thing is that's on the stage? I only asked that because wandering through the halls yesterday after getting the badges I heard a bunch of 20 somethings talking about what the Konami code was and they were listing it off wrong. So um if you are that of that age you're going to get a little bit of a history lesson. I've seen this demo, this is awesome. Get excited. Let's give Alan a big hand. Thank you. Well thank you very much. This is a very very technically challenging series of live demos. I have an immense number of things on the stage that can and will go wrong so please feel free to make fun of the equipment when that happens. The equipment not me. Um hello everyone I am Alan Cecil. I'm also known as Duango AC. I am the president of the North Bay Linux users group. I'm also a senior engineer at Sienna. Uh and I am a tool assisted speedrun advocate and an ambassador for taskvideos.org. Um so I want to talk about uh speedrunning and why is it okay there we go. Uh speedrunning with human limits. So early on um people wanted to play games fast because after you've beaten a game it's a lot of fun to try to beat it again. Uh faster right and some games like Metroid especially Super Metroid reward you for playing faster if you complete Super Metroid in less than three hours. Uh she ends up wearing a bikini for some reason. I didn't do it. Um so there are now categories uh that people tried to speedrun games in. Everything from any percent to uh 100 percent get every item in the game as fast as you can. To esoteric categories like low percentage no major glitches. And now most of these demos are most of these records are stored on a website named uh SpeedDemosArchive and there's some other websites like that that also track the fastest completion times. Um now there's a lot of strict rules. There's peer review of videos to make sure that no one is cheating that no one is using keyboard macros or any kind of uh anything other than the human uh their own human ability. And I have to tell you they're really entertaining. Now one of the places that these are uh widely shown is at Games Done Quick events uh Games Done Quick dot com. There's an awesome Games Done Quick and the winner that benefits the Prevent Cancer Foundation and and a Summer Games Done Quick uh every summer that benefits doctors without borders. And there's usually some crazy stuff going on there. Uh for instance here we have Mario Kart 64. Um you can see he's kind of out of bounds. Um that's because he's tricking the lap counter so that he only has to go around the course uh one full time and then he can trip the lap counter after he completes it. Um here's Super Metroid he's uh I'm sorry Metroid the original Metroid. He's Lured or she technically it's Samus. Has Lured an enemy from an adjacent screen and is using it to uh to freeze it to use it as a platform to sequence break the game. Get someplace you're not supposed to be at that point with the items you have. Now there's all kinds of other things that happen at Games Done Quick events that are absolutely insane. Uh this is half coordinated. Uh he cannot use for the most part he can't use the right side of his body. So he completes games using only one hand on the controller. And it's insane watching him play. Uh there's also been some crazy things like uh this guy completing all the way up to Mike Tyson uh in Mike Tyson's Punch Out blindfolded. Just listening to the game audio. Just insane. So this is clearly beyond the standard limits of what most humans can do. But tool assisted speed runs or tool assisted super plays go a step further. We're not really interested in human limits anymore. Now we're interested in what can this piece of hardware really do. If you pushed it to the limits of what the hardware is capable of. And TAS is used as a noun, a verb. I passed this. This person's a great passer. You'll hear me say the word TAS throughout the whole talk. Now the history of tool assisted speed runs is kind of interesting. Uh back in the 90s the game Doom came out and it had a quick save button and a quick load button because let's face it it was kind of a hard game and you were likely to die a lot. Well they added re-recording tools and that allowed you to play through a game and record your progress. And at a certain point somebody figured out you could do it in slow motion and keep loading the save states over and over again until you got a pretty good completion and in 1999 roughly Doom done quick came out and completed the entire first game in 19 minutes and 41 seconds. This was followed up by a couple of other ones. There's a 14 minute and 2 second completion of Doom 2 for instance. So it's it's it's definitely been one of the the first widely known tool assisted speed runs. Now in 2003 a video surfaced online from somebody named Morimoto and it was a little bit let's just describe it as controversial because Mario was flirting with death, getting an insane number of one ups, literally walking through walls and there was no context for where that video came from. Now it had been posted on a Japanese website with appropriate annotations to describe that it was done with an emulator in slow motion with save states. But it was the context of the video was missing when the WMV file in 2003 pre YouTube days got circulated around the Internet. And the problem was that it was in human skill and display and really tools meant hardware limits became the only limits. But if you don't say that you're testing the hardware limits, people get really upset. So passing. It's kind of like the doped Olympics. I mean, let's just be honest here. Competitors should admit to doping. Let's just be honest here and videos made with test tool should be labeled. And there's a guy named Bizquit that in 2004 created NES videos to track tool assisted speed runs the same way speed demos archive was tracking in game human completion times. Now there's that's now gone beyond just the Nintendo Entertainment System. This console here it's now moved on to many, many consoles. And there's now everything from modern consoles like the Nintendo we through handhelds at task videos.org. So I know live demo like we're only a few minutes of the talk, but let's do a live demo. I'll talk about the console verification part in a little bit, but just know that we made a game in an emulator. We set up a sequence of button presses. And I'm going to show you what those button presses are using taskbot. So this is where the video might go completely haywire. And I don't know what's going to happen. If you see somebody running from the side of the room. Yeah, just bear with it. Thank you. I said turn it down not crash it. I said that there was going to be at least one catastrophic thing. I wasn't kidding. I don't even know what happened there. I've never seen that happen before. And that is something you can quote me on because it happens all the time. All right, let's do this again. It's still pretty loud, but I don't think blowing in the car to work. But hey, it worked last time. But I do want to make absolutely certain that I don't have like wires crossed or something funny going on with power. Because obviously if there's not a good ground, things could be weird. But let's just try the there. I kind of want this one to work. This one should work. The only thing I'm going to double check just to make sure nothing else got funny. The only other thing I can think of might be power, but we'll try this one more time. Oh, and we lost the signal too. Remember I said live demos, at least one of them was going to go completely haywire. Well, I don't know where our tech guy is to fix this. And I'm not about to go touch it. At least it's... Yeah, I'm a little bit concerned here. So what's up? Besides, this thing's durable. Well, welcome to the first live demo that goes wrong. That's okay. I'm going to do the rest of the demos entirely on the Super Nintendo. But of course, we will have to get somebody in the room to fix the scrolling. But I'm very confused by that behavior. I've never seen it before.  But that's okay. We'll just move on. This is going to cause a brief audio pop. I apologize in advance. So with any luck. So we probably are going to have rolling video at first. Apparently no video. Okay, we can barely see it. So I'm going to keep going through some slides here. This was made with one of a number of emulators. There's several emulators out there. FCEUX, there's LS&ES, which this run was made with. This is the Super Mario World Game for the Super Nintendo. It is a very good emulator with a lot of useful tools on it. And I know that it's going to be impossible to see with the scrolling. But Mario is doing some really unusual things right now. Yes, he just got about four Yoshi's. So it's kind of hard to see right now. But basically what's happening is we have the ability to back up and try things as many times as we like. And that means we can do things with frame precision. And right now what we're doing is lining up the object attribute map to be exactly the way we want it to be. There we go, our good. Unfortunately I think you're going to have to do that every single time. Okay, so that's a heck with the slides. There's other re-recording frameworks. I made one called NetHack uh, tax tools that we've used before. There's hourglass for windows things. Everybody's looking at this video anyway. It doesn't really matter. Um, so this was uh, done with a BS NES core which was very very accurate. And that's incredibly important because in just one second, look at these visualization boards right here and right there. That's the actual button presses we're sending to the console. So yes, Taskbot plays Super Mario World. Um, yeah, I'm just going to skip all that. We'll come back to that some time. So, Taskbot plays Super Mario, what? Oh, oh, I'm sorry. It's Super Mario Brothers in Super Mario. I get it. Um, I said this was a live demo. If somebody wants to come up here, you can definitely play this if you wanted to, uh, except I forgot to bring the controller. Sorry, that won't work so well. Um, this is fully playable. So we took Super Mario Brothers, a game from the original Nintendo, and placed it on the Super Nintendo, which was never designed to have it. So we took a previous console run from here game and programmed it through the controller ports on completely unmodified hardware. Now, this was done by Master June who set up the button presses and by somebody named P4 plus two. And it's a really complex series of events. But there's a really good YouTube video by dots are cool. Um, uh, that value is kind of loud, but that's okay. Just ignore it. Uh, so what you're basically seeing is, uh, he was going back and forth and rearranging objects in the object attribute map to basically write op codes in RAM in such a way that when we did certain things, it treated the location and memory that the controller is stored in as something it should execute. And it did exactly that. It ran what we put on the controller and allowed us to, well, you can either trigger the credits or you can take it one step further and do crazy stuff. Um, but that's not not good enough. This one was this ran at 184 kilobits per second, which is nice. You know, it's it's cool, but we can do better and we're going to. So I need I'll need to restart, which means that it's probably going to mess up the video. Uh, one of the interesting things about the, uh, about the original, uh, consoles is that they are running at a resolution best described as 240p. They played trickery with CRT TVs. So, um, we have had a lot of trouble getting captured to work. It's actually been a bit of a pain. So I just erased the save game and that's going to prepare me for, uh, doing a, uh, another run. Let's see. Alright, here we go. So this is the same game and this time, oh good, the video isn't rolling right off the top. Okay, this is good. If we're lucky it'll, it'll stick with us unless we can switch consoles. Um, so this is the exact same game, but if you're able to see it, you'll notice that the video is, is going to be using slightly different technique. This is a different exploit than the first one. Yes, there are more than one, there's more than one way to blow up Super Mario World. Um, and this one is going to use a slightly different technique. So, one of my earlier slides I was talking about, uh, the different devices that we have. Well, the newest device we have is from, uh, is a board called, uh, Tasselink board and has a very high data rate. The previous boards made by somebody named Tru, who's actually a DEF CON regular, uh, Tru's board was able to hit 184 kilobits per second, uh, based on his, uh, multi replay board. This one is using an FPGA from Papilio and we're able to achieve data rates of, uh, much higher than that, which you'll see here in a second as soon as he gets done screwing around with a charging check. Right about here. I love the scene right here. Just, just watch what he does to this check is an image that was written to the console at 900 and I want to say 920 kilobits per second. Um, keep in mind that the maximum rate that these consoles usually ran at was about three, I'm sorry, about 480 bytes per second. And that was like that most. So for us to shove that much data through it is, is kind of impressive. I'm, I'm amazed that this console manages to hold up. Um, I need to actually back up a little bit and, uh, cover a few things that I skipped over. So I'll just go to here. Uh, there were a bunch of early console devices. Uh, Tru was the first person to attach a, a console and, uh, and get, get it to, to do button presses. And it's actually a very simple protocol, especially for the original Nintendo. And one of the things I was going to talk about during the original video I planned, there's only five wires. There's just five volts in ground. There's a latch wire that says latch, hey controller, I'm about to ask you what buttons you're pressing. Clock, give me the first button is a being pressed. Uh, one or high voltage if yes, none or zero for no. And the only other line is a serial data line out from the controller sending that information back to the console. So what this guy here does is pays attention to that, that feed and sends appropriate responses. So the first device that this was tested with was all the way back in 2009 and a board from true. But in 2011, somebody micro 500 who built also this, this tassel board, micro 500 made a device called the NES bot that based on a breadboard, you can see here in the lower, lower corner, that was able to complete Super Mario Brothers one. And it was used at one of the very early summer games done quick events to complete Wizards and Warriors 3 and Super Mario Brothers 2, although somewhat comically. And by the way, that what you see on the screen if I know it's really tiny, but there's just a very few number of people in the audience. This was one of the early summer games done quick events that didn't have very many people. Now this room would be looking a little bit more like Defconn here. But there were a couple of other boards. There was a Droid 64 bot that could do N64 games and micro 500 made one of his own in 2012 using a propeller board. But the task spot, this, this guy here, a Rob holding a random device with Legos on it. That kind of happened a little bit later. So in 2013, we had an opportunity to to again go to summer games or awesome games done quick and present and true built a device from scratch based on a micro chip device. And it was it was a very, very good device in the sense that it was streaming capable, very inexpensive, a little bit fidgety with wiring because of the punch down of the screw down blocks that we used. And it had somewhat limited data rates, but we were able to do some really impressive things on that. One of the first things we did was a snake and Pong on top of Super Mario World. Well, I took a I eventually this was like the first prototype, I just zipped item together. I took some, some Legos eventually shoved them together and I called it Robberry Pi because at that point it was being fed by a Raspberry Pi posted this run on awesome games done quick saying, Hey, I want to want to go to the event. And immediately Mecha Rector says, Hey, I want to see some of that task bot action exploded. I never called this guy task bot. It just happened. So task bot is nothing more than a Rob robot from the 1980s that was shipped with the original Nintendo console so that it didn't look like an old Atari video game console with some Legos and a replay device. And that's pretty much it. Now the multi replay device is when I mentioned earlier that was capable of putting Super Mario Brothers inside a Super Mario World. And there was also some other really interesting developments. There's a Game Boy player player and there's one I haven't mentioned here that's able to play DS games. So we already went through all of this. I'm going to fast forward. But I really want to. Oh, and by the way the faster data rates also allowed us to play Super Mario Brothers one, two, three and lost levels at the same time with the exact same sequence of button presses completing at about the same second. It was. Really quite impressive. Very, very crazy. We just did that a few weeks ago at Summer Games done quick. So I want to step back for a bit. I don't know how I'm doing on time. Okay, I'm doing all right. I'm actually doing just fine on time. I want to really step through and go in a deep dive into one of these exploits and really break it down so that you kind of understand some of the sequences we go through. So I'm going to start with a game called Pokemon Red. Now. Pokemon Red is a really broken game. You'll see how broken like it's really broken. But a handheld Game Boy is kind of difficult to wire into. Now we've done it, but it's not exactly a lot of fun. So this is a Super Game Boy cartridge. This has an entire Game Boy processor, a Z80 processor, a code named a DMG inside of this card. And it communicates with the Super Nintendo and allows us to, oh great, right when I need to swap video and I don't know where he went. All right, well I hope it works. So that allows it to use the controllers, which is great for us. It means I don't have to touch anything. Now I have a wire here. And this wire is kind of an interesting little thing. There we go. All right, that's already full of bake. This wire has a little expansion board connector. On the underside of the console there is this not very often used expansion board. They eventually used it for a cancelled project that connected the CD drive to this thing, but it was never really implemented. Now we're using it because it exposes a reset pen that we kind of want to play with. A play with. Yeah, I'll go with play with. So and hopefully my video signal stays. Any luck? Yay. All right, we're good. And we don't really need a lot of audio for this one. It's there's not really, I like the game audio, but I've got to tell you when I was testing this I listened to it over and over and over again and I got really tired of it. So what's happening right now? We're going to delete the contents that was there previously. And there we go. And we're going to start a new game and we're going to set very specific parameters. So unfortunately, it's kind of slow menuing. It takes a while to get there. So I'll kind of explain it in advance. We're going to name the player's character red. And we're going to name the rival a very unusual name. We're going to name him RxRxPK. There's actually a PK symbol. And the reason we do this is we need to preset up certain memory values to be in our advantage that we'll be using again later. So he said, yeah, we're about to start our adventure. Except we're not going to bother getting very far into it before we save. So we're going to save and bam. So what we just did is we reset while we were saving the game. Now I don't need this wire anymore so I'm going to pull it out. That allowed us to write a completely valid game header that said, yes, your player's name is this, your rival is this. You have, wait, how many Pokemon did we have? Oh, we left FFs in there. Oh, well. So you can kind of see where we're going here. All right. So now we're going to start and load the save game we just used. So again, this is kind of slow. It'll take a little while to get here. I'm going to get it. I'm going to get ahead of myself because this section goes rather quickly. There's just a lot to explain. So what we're going to do is load the save game we just created and it is a valid save game. But the list of how many Pokemon we have says we have 255 long. And that allows us to go beyond the area of memory we would normally be able to go to. And right here, you'll see we swapped Pokemon over the area of memory that contains our items. Now that means that we have to do a couple of other switches so that we don't crash the game, by the way, but I'll get to that in a second. That means that we can now delve into our item list. And you can see here there are some items that are stored as a two byte pair, one byte to say what the item's name is and one byte to say what the quantity of it is. So we just tossed, well now we're switching where items are to move them in memory, but we just tossed some of an item. We're going to do it here. So TN 25, we're going to toss 24 of those. Well, whatever value we started with in memory, we've just thrown out a bunch of items and we've reduced that memory by 24 in RAM. So this allows us to directly manipulate memory, but we can only manipulate every other byte. Fortunately, if we go back and swap Pokemon like we're doing right here, it offsets memory by an odd number. So what used to be an identifier is now a value, or a quantity value that we can then throw away. So now we can write everything in memory, but we have to be very careful because some items, if you throw them away, every item of that category, you can never touch again. Some items, if you throw them away, will crash the game. And some items will crash the game simply if you look at them. Not so helpful. So there's also another thing that we're doing here. We're obviously writing bytes in memory in order to, in order to create a routine that will allow us to read from what's on the controller and store it in memory. The problem is the Super Game Boy cancels up and down and left and right. So if you try to press both, both those buttons at the same time, they just get zeroed out. So to get around that, the routine we're writing right now, we're literally writing a program as you see. It reads, stores it in memory, reads again, stores it in memory, does a subtract between the two, stores the result in RAM in one position and then keeps writing in one after another. And when it gets to the end, it writes over a jump sequence to go execute what it just wrote. And what it's writing right now, which you'll be able to see on these visualization boards, is a rather substantial payload. And it takes quite a while to write it all. So anybody recognize that? Has anybody ever been to twitch.tv? Well, get your smartphones ready. This is the live demo part. This is the part I like the most. Ooh, you know, it really, really helps. So it really helps if you actually have an internet connection when you try this. So we have to take a quick pause and hope that this cable reaches without causing anybody too much pain. So yes, we really are going to connect a 25 year old console to the internet. And you get to ask your Q&A over the chat session if it works. Nice. We've already got some action here. All right, somebody typed something and it will appear on the screen. I assure you. So what you need to do is let me quickly get here. I will actually type out the address.  Have fun defeating that. It can be hacked. This code is all on PPT IRC on Git. You can find the swear filter in there and defeat it to your heart's content. This is Defcon. Have fun. Knock yourselves out. So here's what we're going to do. I'm going to talk about a couple other things. See if I can find the channel that everybody is in. I know I've got it in here somewhere. There it is. Oh, wait a minute. I know what's happening. We're playing back a screenplay because I never moved the file over. So what you're actually seeing on screen because I couldn't see it on down here, you're seeing the exact text that we put on screen at awesome games done quick 2015. It was an entire screenplay of conversation. I'm just going to let it run because it's actually kind of stupid, poorly written and hilarious. I had my own script of things I was supposed to say and it never did because it was just too awkward.  I didn't name the article journal article, but the journal is absolutely fantastic. You can find a full write up written by myself Ellari, the author of the emulator and P4 plus to the author of the chat interface at POC GTFO issue 10. Just search Google for that. It's mirrored all over the place. It is there's a lot more details than what I covered here. By the time we get done doing all of this, we escape the Super Game Boy. We tell the Super Game Boy that we want to execute something in the Super Nintendo's memory space and it lets us do it because there's actually a there's a command that lets you do that. There were only there's only one or two games that ever actually took advantage of that feature, but that's there. Once we get to the Super Nintendo, we're no longer limited to one byte per frame. In fact, we were at one point only able to enable the frame because we had to subtract them together to get around the button limitations. So what we ended up doing is after we get to the Super Nintendo, we get to a data rate of two bytes per controller and we tell it, oh, you actually have a multi-tap attached. So you have two controllers on the first controller port and two on the second. So you get eight bytes per frame and 60 frames per second. So it gets us about 480 bytes a second if I did my mouth right. But that still wasn't enough. So we told it, oh, and don't just read once per frame. Read eight times per frame, 60 times a second. So that gets us to a data rate of 3.8K per second or so. Oh, four, four. Well, we're in somewhere. I just don't know where we're at. Oh, yeah. There's me. I just typed test and it worked. So there's all kinds of crazy going on, but that's OK. This is going to be at the end of the pre-recorded input in just a second here. While that's playing through, there's so many more details of this. There's a block loader we program in afterwards. It's just a really, really intense, technically challenging process that we had to go through to do this. Did Frank or Z come through? Wow. So it looks like because I ran the wrong script, it's getting some characters out of order, like hilariously out of order. Hack the planet, huh? Uh, that's like hilariously funny. This wouldn't be a live demo without things failing. So let's keep going. So this is my call to action. If you want to join in on the fun, you can go to twitch.tv slash to Wango AC. I am going to go ahead and, well, that's a lot of Frank or Z. Twitch the twitch. Well, it's a little bit, a little bit messed up, but I can at least see it on my screen here, even if it's not completely correct there. Oh, well, go ahead and ask any Q and A questions you have in the chat. So again, you can go to twitch.tv slash to Wango AC. Subscribe while you're there if you like, I don't care. But there's one other thing I want to talk about. We recently found a very, very interesting glitch in Super Mario Brothers 3 that I wish I could show you on the real console. What we found out is that it is possible to go from boot to the ending of the game in literally 16 frames. I'm not kidding, it does take quite a few button presses per second to do it, and it doesn't exactly treat the pallets very nicely. Not everything gets loaded into RAM, but it is a valid completion of the game. It properly goes to the end credits. So this happens because of an interesting choice they made. 10 minutes? Got it. So when they released this Nintendo hardware, the original NES in America, they had a problem. They released the hardware and then discovered that if a game used DPCM audio and the controller was asked for what values it was holding, at the same time that there was a collision on the bus and the controller input may or may not be dropped. So to get around it, they asked the controller for input. Two milliseconds later, they asked the controller for input again. And if it's different, they ask again. And if it's different from the previous, they ask again. And if it's different from the previous, you can kind of see where this is going, right? Infinitely. This allowed us to keep giving the console a different response for what buttons we were holding every other time that it asked for input. And eventually, it tied it up until the next frame's processing started for the raster input that displays a status bar at the bottom of the screen. And it was still doing this, that we were still keeping it busy with this other loop. So what ends up happening is it drops execution right at the bottom of the stack and slides across a series of breaks and no ops directly into the addresses where the controller data is stored. So on the second frame, instead of screwing with it and giving it different input, we correctly give it input like it's expecting. The first byte is stored as an opcode in memory or is stored as a byte in memory and treated as an opcode. And we type the value that says jump to. And on the second controller, we type the value that says end credits or the address of the end credits. So in fact, we literally tell it to jump to the end credits, 16 frames or around a quarter of a second after starting the game. Now, this is possible because of tools like Binary Ninja. And I had plans to do a full demo and I'm being told I've only got 10 minutes, so I'm kind of running out of time there. But Binary Ninja is definitely a lot more flexible than Ida because there's some ability to add in other mappers. It can handle the 6502. It can show all kinds of useful things. We were able to find the actual program code where the controller was being pulled and figure out what it was doing and find the exploit. So am I cheating? No, I'm not really cheating. I'm just looking for technical challenge and visual entertainment and all of us are. I'm the presenter. I'm the organizer of the games and quick events. But this is so much more difficult than anything I could do on my own. There's one person who's really good at hardware. There's one person that's really good at emulation. There's one person who's really good at making the actual replay movie files. There's one person who's a really great glitch finder. It takes a lot of different people. And why do we do it? Because we've been able to raise over $200,000 for charity between the five different events we've done at Games Done Quick events. And just this summer, yeah. That's really what motivates us. Just this summer we had an hour block of time at Summer Games Done Quick 2016. And in an hour we raised $40,000 for Doctors Without Borders and the marathon as a whole raised $1.3 million. And that's a huge success. So I'd like to thank Micro 500. He made the task link board here. Ellari made the LS and ES emulator and also heavily contributed to the block loader and a lot of other things that worked for Pokemon Play's Twitch, which is what you're seeing here. This is Pokemon Red playing a Twitch chat. P4 plus two wrote that actual Twitch chat. Masterjin is the one that figured out the exact sequence of orders of placing everything. Tru, of course, made the earlier devices. Total is the one that found the Super Mario Brothers three glitch. Cypher Text is behind, and Rusty are behind Binary Ninja. AIS 523 helped with the DPCM glitch info. And was hugely helpful in getting these slides put together and helped in the proof of concept article. Greenfly helped me set up today. There's a lot of other people at taskvideos.org that I don't even have remotely enough time to mention. So now, let's see if there's actually any sanity in this chat and see if there's an actual question I can answer. It's Twitch. It's Twitch. No, I am error. Gun cap up. So if you do want to ask a question, I have exactly five minutes, I believe? Five minutes? Wow, somebody's got some potty now. Pretty good latency. Yep, I imagine. How many viewers do I have now? Anyway, I'm just looking. I'm looking at Twitch chat via IRC because that's how the spot works. Let's see, are there any serious questions? Have you ever seen a zombie come to tea? No. That's a very interesting. Is this easy mode? Not exactly. What's your favorite sandwich? I have no idea. Probably chicken pesto. What the heck? Okay, when I said Q&A, I meant Q&A about like this. Drinks later. Yes! Drinks later, definitely. I'll be standing over there. I'm gonna need one after this talk. Do I know what I am doing? No, sort of. Are they under the truck? How does the bot work with timing? Okay, this is a very good question. This is the first serious question I've seen. So on the original Nintendo, I mentioned that it actually asks for input more than once per frame because it has to make sure that it's not running into this DPCM glitch. On many games, not all but many, any that use DPCM audio. So that means that we have to put it in a windowed mode and we have to ourselves keep track of which frame we're on. And in fact, that's the secret to all of these runs anyway, is a tool-assisted speed run, which is typically run on an emulator rather than on the original hardware, is nothing more or nothing less than a series of button presses showing every frame's worth of input, one frame after another. So we're able to convert that to run on a console, but we do have to pay attention to the little nuances that the console is going to ask more than once. So we have to keep track of which frame we're on and send it only the right input.  TaskSpot always kills the animals. If any of you guys know what that reference is. So there's save the frames or save the animals or vice versa. At GDQ events, they always play Super Metroid with usually a two to four player race and inevitably there's up to $200,000 contributed of people watching and donating on either side for a donation incentive. If they decide to kill the animals because more donations went to that, they bypass going to release some animals that are trapped on the planet before they leave the game, which is faster and saves frames if they have to save the animals that waste time. Can you use this for malicious use? Yes, that's the whole point. In fact, one of the reasons that we wanna do this, and I'm gonna see if I can find this, I'm gonna have to go back like crazy because I've got so many slides here. The primary point I actually wanted to make and I'm really glad that somebody reminded me of this is that the difference between the tool assisted speed run community and the InfoSec reverse engineering community really isn't that substantial. A save state and an emulator is nothing more than a VM snapshot. A glitch is just a vulnerability waiting to be exploited. An arbitrary code execution is doing just that. Console verification in a lot of ways, it's kind of like an evil made attack. We're acting like a normal controller but we don't exactly have the best intentions. So a tool assisted speed run because the emulators have so many tools to be able to step forward, look deep into memory, look at all the aspects of the CPU registers, every last iota of what's going on and the ability to try things over and over again, it is a fantastic place to start looking for glitches and games and start looking for and refining techniques for reverse engineering. So I encourage you, go to taskvideos.org, check that out. I'm just gonna hold this down until I get to the end. If there's one last serious question, I might answer that, but I have a funny feeling there's not gonna be much. Where can I catch him, you two, I have no idea. More games soon, yes. We'll be doing another round at Austin Games Done Quick 2017. More information at gamesdonequick.com. And I think I'm just gonna wrap up with this last question. How do you mine for fish? What the heck? Do I play Pokemon Go? No, I don't, but I think it would be really funny if Taskbot did. Let's see. Has used tasks as to fuzz. Sort of, not really. We'll get back to you on that. Can I, can you do something useful? Yes, I can do lots of useful things. He can do all kinds of, he can beat games really fast when everything works technically. What is my favorite Taskbot exploit? I have to say it's gotta be this one. I mean, I know it's kind of, other future console, I mean it's kind of, DEF CON is great now. Can we all agree on that? All right. Yeah, Pokemon Play Switch by far is my favorite. I actively was involved in making the movie for that and had a deep part in the technical aspects of that. So definitely my favorite. Hey, I wanna thank everybody for participating. I'll leave the chat up. You guys can continue to talk. Thank you very much.


Live from San Jose, California, it's theCUBE, happy adaptive flash launch, brought to you by Nimble Storage. Now here are your hosts, John Furrier and Stu Miniman. I'm John Furrier, my co-host Stu Miniman, we're here live at Nimble Storage for exclusive product announcement, Stu, Nimble Storage, big product launch with the large part of the market in storage, in the mid-market, really exploding, a lot of folks focusing on the high end, talking about all flash, this is a hybrid approach. What's your take before we get into the announcement? Yeah, John, so, you know, Nimble's been a fun company to watch. If you look, you know, we've been, you know, talking about storage on theCUBE since our first show at EMC World in 2010, talked to all the storage players and, you know, where's the innovation? What's really driving change in storage? And there were a few IPOs and a couple of them stumbled and Nimble's going strong. So, good revenue year over year, good differentiation in their product line and excited to see what they're going to talk. We've got some of their customers on, we've got some of the executives on and, you know, good things to do. We've been covering the flash market storage, obviously, for a very long time. Obviously, the convergent infrastructure is the hottest thing on the planet right now. You're seeing success at many levels where performance, cost per gigabyte and also throughput are huge issues. And it seems that not one trick pony kind of wins the game. So I want to get your take on the competitive landscape, specifically around the competition, right? We're seeing a lot of folks focusing on the high end, exclusively looking at transactions. Okay, that's great. But as flash goes mainstream, as a utility, as a technology, what's the implications for just normal mid-market enterprises? Sure. So, as we know, the enterprise tends to move a little slow. So if we look back to the founding of Nimble, you have people that came from the data domain, building new storage efficiency architectures, using things like, you know, thin provisioning and compression and flash to really change the economics. So rather than kind of the old way with kind of tiering, you know, the new way is, you know, really using software to be able to really manage how it's done, Nimble does what's called the castle architecture, which I'm sure we're going to talk about with Suresh.  And, you know, they got checkboxes and a lot of character, John, you much can convert to infrastructure, they've got SmartStack, there's a whole lot of places that Nimble does fit into scale-out. We're live in Silicon Valley here at Nimble Storage Headquarters in San Jose. This is theCUBE. We go out to the advanced extractor, Sid Linois, big announcement here with Nimble Software. Still, I've got to talk to you about the company. One, they're a public company. They've done well with their performance. The numbers are out in the open in the public market. So it's a real marketplace on the competition side. There's a lot of private companies that have outrageous valuations, mainly in the all-flash array. And they're getting a lot of attention. Some say that's not a real market. That's just more of a private equity market. But what is the difference between hybrid and all-flash rate? And can you tease out why what they're doing in this hybrid approach is so important? Yeah. So, John, you're right. Right now, Nimble really plays really well in kind of the fat middle of the market. So then that mid-range customer, and as flash prices go down, the expected expectation with adaptive flash is that flash is going to be even more part of it. We know that Nimble is going to push higher up into the enterprise. Classic disruption that you start a little bit smaller and then you go into the bigger accounts. The financials, as you said, are real good. They did over $125 million last year. And they've got a $1.7 billion market valuation. So they're doing good growth. Their existing customers are buying more of what they're doing. So interesting to see where they're going to go with it today. And absolutely, we're going to dig into that discussion of hybrid consumers, all flat and gray. Where's their real revenue? Because Nimble's got strong revenue and good valuations, but not open the moon. Stu, I got to say to the folks out there, this is a huge Silicon Valley success story in the industry. You're seeing a company that's a durable company pumping on all cylinders. Nimble's software, really, really successful here in Silicon Valley. So I got to ask you where they go next. Obviously, with the mid-market being a great growth driver for the company, this should set the table pretty well for the channel strategy. I'm hearing from a lot of channel partners out there over the past few years and the past Cube shows we've been to that they're hungry for solutions. How does this product fit into the channel? Is it channel friendly? Do you see an opportunity for Nimble in that regard? Yeah, John, absolutely. The mid-market is owned by the channel, and every one of the big storage guys are trying to fight for that channel. And Nimble's there. One of the things, John, that's really interesting is if you look at margins, Nimble's actually getting 10 points better than the EMC's in that absolute world. So if there's margins, that means there's more money to pay the channel, and we know they're going to operate it out there, so they're going to make money. And we've talked convergent structures, the big company, the smart stack reference architecture that Nimble has in partnering with Cisco. And of course, we know Cisco's been running away with that convergent market with what they're doing with NetApp, EMC, and starting to spread out to a broader and more diverse portfolio of storage partners. The criticism on Nimble has been that they might not have to depock us like some of the big players out there throwing money at this market, and also that all flash arrays are getting attention, specifically from a modern perspective. All flashes can say, oh, that's real modern, and also the dollars in terms of the big whales that are going to come into this market pretty heavily, like EMC and others. So we're going to dig into that with the folks here, but what's your take before we get the guests on? How do they compete? Is it modern? And how do they compete with the go-to market? Yeah, so I know we'll bring David Floyer on later to really go into what is a modern architecture, but, you know, Nimble was founded in 2017, launched in 2010, so this is a modern architecture. It does fit into scale-out environments. We're starting to see a line blurring between hybrid guys and the all-flash guys. T-Gile made an announcement within the last week, and they have a full, all-flash version of what they're doing. We'll see how Nimble's environment matches up to what they're doing. The register actually wrote an article kind of teasing out is, did T-Gile be nimble to the punch with kind of this new architecture? So these guys are obviously a diamond in the rough. The question we want to get into in this product now is, does this move up market? Do they have the ability to go up market? What does their product portfolio look like? And what are you expecting to hear today from Nimble? Yeah, so absolutely, John. I mean, every company has it's going to move up market. It's much easier to move up market, especially the channel guys are going to work with bigger deals, and customers are buying more from their environment. You know, more repeat customers that their steel sizes are going to grow, and they're going to be able to extend them to work with them. So we're here at Nimble Storage in Silicon Valley. We're live as the queue. We're covering the exclusive product to Nestle from Nimble Storage. We'll get into it. We don't want to release the data too early. We're going to go live to the press conference here with all their customers. But Stu, I got to ask you, where do they go from here? Can Nimble continue to keep pace with the change of the industry? One of the things that is on the mind of customers is, can the vendors, can the technology providers like Nimble move at the pace of the market? Obviously, we have a good market in the sense that the flash prices are coming down. The question is, can the modern infrastructure, on the cost perspective, through IOPS, throughput, and cost per gigabyte, all those three things are in play, which plays well for this hybrid. What's your take on this landscape, how fast it's shifting, and what is Nimble doing and have to do to be competitive? Yes. So John, architecturally, I like what Nimble's done. The biggest criticism I've seen is, you know, Nimble's a storage company, and the storage market is changing. Silo's are breaking down, because infrastructure's driving change at the pull of storage back into the compute layer. What, at Wikibon, we call the server sand market, it's changing things with VMware, doing the vSand, when the Tanix is doing some of these others.   You know, it's all flashing into separate array.  Before we get going, so I want to ask you a final question around Nimble. Is it a technology advantage they have, or is it just timing, positioning in the market, product portfolio, what's your take? Is it the engine of their technology, or is it the timing of the market and their positioning, what's your take on that?  So you see the architecture of the hybrid being a critical thing, and also the technology. Yeah, right, it is a modern architecture, it hits the checkboxes, what companies have been looking for, if they want to make a partner to work with their data, and John, more than just storage, it's also the backup, backup's a big piece of it, so we need like net-up pad before most of the software is just all in there, so I don't need to buy a separate box, I don't need to have extra software on it, but Nimble's going to pull that storage, primary storage and backup in a nice press-off. Well, hybrid's a great word, obviously we hear hybrid cloud as a key bridge to the cloud, a lot of modern enterprise, we should call it the cube, the hybrid cube, we should create a hybrid cube just to kind of get in line with the trends. Yeah, we're doing it, we're the chain-arising Yeah.  As I always said, we said in the cube you can't fight fashion, and having a composite architecture like what these guys are doing hybrid really bodes well for what the people want, they want an engine that's going to be flexible and adaptive, they call it adaptive flash here, more importantly the developers who are writing the software want to have turnkey infrastructure that can be horizontally scalable and also work with open source and other things, so I see a great opportunity for the software side of the house, certainly on the storage, whoever can create that enablement for horizontally scalable DevOps, cloud, whatnot, that's the winning formula. This is the cube, we're live here in Silicon Valley at Nimble Storage for exclusive product launch, we'll be right back with more exclusive coverage right after this short break.