So today, I'll be talking about a fine-grain approach to algorithms and complexity and at the end I'll try to tie it up with What you as cryptographer study? all right, so What are the problems that I'm going to talk about? Well, I Love algorithms and what what do people in algorithms research actually study? So when you open an algorithms textbook, what do you see you see the following? This is the fundamental questions of algorithms research is how fast can we solve fundamental problems in the worst case? Okay, so I'll parse it for you a little bit. You probably all know what it means But let me do it anyway to so we're on the same page. So we have some function. We want to compute It's computable. We have some reasonable model of computation such as a Turing machine or a random axis machine This reasonable model of computation defines base basic primitives Which take constant time for operation and now we want to compute our function on n-bit inputs on that machine and now we We want to know how many operations does it take to compute a particular input? And what is the worst case asymptotic running time? That is as the length of the input grows What does the runtime look like and in particular? We want to get a handle on what is the best running time that we can achieve with an algorithm now? What what is our holy grail? It's a linear time algorithm. So some algorithm that runs in Time this linear in the length of the input And why is this interesting? Well, it's for most of the problems we study. We actually have to read the input So therefore it's asymptotically optimal up to constants. So this is what we want and The good news is we have a huge tool of techniques and many problems. We can just solve very fast So we've developed a ton of different Tools they have a wonderful toolbox and we can just use it you give me some problem that you want to solve I'm going to try to throw all these techniques at it and I'll come up with some algorithm Yeah, and so on now Unfortunately, there's also this Big algorithm called exhaustive search. This is the first thing you try now in formal for all problems in NP For example, you have a natural notion of a verifier That is when you when you'd have you have a solution to the problem the verifier checks it, right? so this defines a notion of a search space and There is this algorithm the exhaustive search algorithm that just brute forces over the search space and this is and Unfortunately for many problems. This is the only way we know how to solve them. There's no significantly faster algorithm and the even in the 50s for good or wrote a letter to von Neumann and he asked Can we improve over exhaustive search in general for the problems we care about? And we don't have the answer to this question and this is something I really care about And this is what this talk is about partially, okay so As I said for many fundamental problems We just don't have a very fast algorithm not even anything that improves upon the brute force algorithm exhaustive search Okay, so I will try to Hand wave a definition of what I think is a hard problem and then I'll narrow it down a little bit So Roughly a hard problem is a problem where our techniques get stuck. We just can't solve it very fast and What are these problems their problems that come from all over the place they come from very diverse areas and They have a very simple often exhaustive search Textbook algorithm. What do I mean by this? Somebody gives you the problem. You throw the unknown tools at it and you come up with a very simple looking algorithm We usually just exhaustive search sometimes maybe like breadth for search or whatever But it's very simple and if you had seen it in the 50s and 60s, you would have come up with the same algorithm Unfortunately for many many decades Nobody improved on this runtime significantly. So this is what I mean by hard So it's very easy to come up with some solution yet improving upon this solution seems kind of difficult All right, so let me give you some examples just so so we see what's going on So here's a canonical hard problem in computer science. This is the satisfiability problem You're given then Boolean variables You're given the formula in conjunctive normal form So a bunch of clauses and you want to know if there's a Boolean assignment to the variables that satisfies the formula now Was the exhaustive search solution so the verifier just checks a given Boolean assignment So the exhaustive search solution is to try all possible Boolean assignments to the n variables and there's two to the end of them And then then after you try them you plug them into the formula and you get a two to the n times mn algorithm All right. Now, what what are the best known algorithms? Well See here K is the width of the clause How many literals you have in the clause and the best known algorithms shave a little bit over this two to the End minus some constant times n over K times a polynomial in that number of clauses now Unfortunately, you know as the length of the clauses grows this runtime actually goes to the 2 to dn runtime so even though we've worked really really hard to improve this running time for many Values of K for each value of K. We have a different, you know running time But as K grows two to dn is where we're at and we could have just done that by done doing exhaustive search so Sat CNF sat I consider it hard because there's no known two to dn to the one minus epsilon time Algorithm for any epsilon bigger than zero Where two to dn is the exhaustive search runtime here Okay Now here's another example of what I mean a Different problem this time. It's a problem in polynomial time So this is the longest common subsequence problem. You may have seen it or taught it in algorithms courses so you're given two sequences of letters the letters come from some finite alphabet for example a CT and G and Roughly you want to know how similar are these Sequences and one notion of similarity is what is the subs the longest subsequence of both of them a Subsequence is a sequence of letters that appears in the same order in both sequences In other words, you can think of it as kind of an alignment problem You place the letters on top of each other you introduce some gaps potentially and you count how many matches you get So the blue sequence is the longest common subsequence here And this problem because it's a sequence similarity problem pops up all over the place you can think of Biology applications for example someone gives you two DNA sequences You want to know are they close to each other? Somebody writes down a sentence introduces a bunch of spelling mistakes And you want to know what is the true sentence and so on so there's lots of examples now It's a very simple problem There's a textbook quadratic time algorithm and is the length of the sequences and you can just run dynamic program and you get n squared Now if if you work really really hard you get a slight improvement of n squared to the divided by log squared of n which is very small unfortunately Neither of these algorithms are particularly fast if then is huge and we remember we want a much faster algorithm like linear time But again, I consider this problem hard because n squared was very easy to achieve Yet nothing better than n squared to the one minus epsilon is no for any epsilon bigger than zero Okay, and alright So now I can redefine what I mean by hard What do I mean by hard you have these very important problems? They have some simple algorithms you'd analyze them you get some function t of n that's much bigger than linear and There's nothing better than t of n in the exponent known from in many decades okay, and There's a lot of these problems. You can just come up with an example. You and it's very easy to come up with them and I want to know why are we stuck? Okay, are we? Is it because like really these problems are intrinsically hard or Because we just lack the techniques Also, more importantly, are we stuck for the same reason? Now if we were stuck on these two problems for the same reason Maybe the reason is that there's just the one algorithm out there Somebody's gonna hand it to me and I solve all the problems that I ever need to solve okay, can I show this and How can I even address this so this is what this talk is about? So what I'll do now I'll show you two approaches in complexity I'll tell you why they they don't quite work and then we'll modify one of them to make it kind of work so as You probably know for almost any model of computation that you pick Turing machine random access machine So on you can prove these theorems. For example, we can show that for any See there problems in end to the C time that are not in like 10 to the C minus epsilon time And there is even tighter theorems known than this And they're just beautiful. However, if I give you my favorite problem, whatever it is Maybe it's sat. I can't even show it is not in linear time Just the lower bound techniques that we're having complex tier and seems insufficient to prove such things And now maybe sat is in linear time. Who knows but we don't think so yet. We cannot prove it So so we have to deal with this lack of techniques. So we have to do something else All right, so then there's this other thing called NP completeness that we now all know and love I said why I think K sad is hard But the reason why you guys maybe think K sad is hard is because it's NP hard not not because of what I said and people really believe P is not equal to NP for various reasons and So because of this theorem the case that is NP hard for okay greater than equal to three and we because we really believe the P is not equal to NP. It must be that K sad Cannot have a polynomial time algorithm. Otherwise people would be okay. So it's a This what we have here is the reason why it's hard is because of this condition that we really believe and And the reason why I believe it is because if you read cook's paper He said it's just him we can't possibly think that we can solve all these wonderful problems and NP in polynomial time It's just impossible yet if you could do this with sad now They would all be important on your time. Therefore. I think it's as hard. So this is why So what we want to do is is have something like this for the problems that we care about Right. We want to say that the reason why I think longest common Subsequence is hard is because well if it weren't hard if I had a bastard and quadratic time algorithm Then I could solve all these other problems and I I don't think I can do that And so on so we want something like this now. Can we use NP hardness to do this? No, because well you can't You can't have a problem that already has a polynomial time algorithm B and P hard because otherwise Because it would be would be equal to NP so we cannot use this particular Hardness, but we'll do something like this so let's Just revisit very simplistically what NP hardness means So NP hardness just you know starts by assuming a particular hardness hypothesis Let's say P is not equal to NP then you use reductions to show that if your problem Q That you think it's hard had a fast algorithm for polynomial time algorithm that P wouldn't be and equal to NP and therefore We we say that this Q cannot have for polynomial time. It must require a super polynomial time this is what the three steps are and Will we want to mimic these steps in our approach? Okay, so this is what I already said we if we use these three steps We cannot show that problems in an quadratic time are hard for this approach So we will change it. All right, so let me take a step back and say Why did we even care about polynomial versus non polynomial in the first place? Is it because we thought polynomial is efficient? No, and to the 100 is not efficient neither is n squared in practice if the n is really large So the reason why is for other technical reasons? For example, remember I said that when we analyze algorithms, we have to fix the computational model But if we only talk about polynomial versus not polynomial We we can afford modeled independence because there's theorems that translate between Computational models and they have polynomial overhead and because this is one very nice reason to think about polynomial versus not Polynomial, but for me I fixed the model so I don't really care about this Okay, another reason is because if I define efficiency in terms of having a polynomial type algorithm Then even I compose an efficient algorithm with an efficient algorithm I get an efficient algorithm because polynomial over polynomial is a polynomial, right? but For me, maybe maybe efficiency is linear time and then I can't use this thing okay, so What we'll do as I mentioned we'll develop this more fine-grain notion of hardness They will distinguish between different Polynomial times and different times in general different functions of the running time of the input size and then it will be conditional because We still don't have the techniques to prove unconditional lower bounds And we'll kind of mimic and be hard. All right, so what I'll do now is I'll Give you the fine-grain approach that we've developed and the way I'll do it is I'll go through the steps of NP hardness and Give you the corresponding steps that we have in fine-grain hardness just to see that there's kind of a direct correspondence So here's just like this Cartoonish view of what NP hardness is You have an assumption P nautical to NP or equivalently sat doesn't have a polynomial time algorithm Then you have this reduction step which says if your problem Q had a polynomial time algorithm then sat would as well and Then you conclude with this conditional hardness because you believe step 1 by step 2 you must have the Q We cannot have a polynomial time algorithm So here's what we'll do instead We will have some other hardness hypotheses Okay, they won't be P nautical to NP. It will be something of the form I pick a problem H for example sat that I think is really really hard because lots of people have worked on it Okay, and then I'll say let's H of N be the textbook or exhaustive Exhaustive search runtime for this problem and then I will assert that H requires roughly H of N time H event to the one minus little of one time on an inclusive size and on let's say a ram So I fix my machine model Then what I do is I have a reduction step when I want to show the Q is Hard then I reduce this problem H to Q in such a way It will imply that if Q had a faster than Q event time algorithm where Q of N is the natural runtime for Q Then I would get a faster than H event time algorithm from problem H Both of these algorithms would run in on the particular model of computation.  So It's not very well defined right now because I haven't told you what these hardness hypotheses are I haven't told you what the reductions are and so on So what I'll do now is I'll go through these steps one by one I'll tell you what hypotheses we usually pick and then I'll define this fine-grain reduction formally And I'll and then I'll give you some consequences things we know about from from this so As I mentioned before Sat we know it's a really hard problem, but not only is it NP hard, but people think it's really really hard And there's these two Hypotheses that have been formulated about set and one of them is the exponential time hypothesis It says that there's no sup exponential time algorithm for Saturday and Equivalently, there's no Delta such that three set for example cannot be solved into the Delta n time There's another one which is truly stronger than this one It's called the strong exponential time hypothesis and if true it would imply a th as well So strong the strong exponential time hypothesis or Seth roughly says that CNF sat on end variables in a linear number of clauses requires roughly to to the end time the original Formulation is something like this for every epsilon. There's some clause with K Such that K sat cannot be solved and two to the end to the one minus epsilon times volume That is a number of clauses time. So this is some Hypothesis and just says this brute force two to the end running time is essentially optimal. That's all it says and What we'll do is we'll just use these hypotheses and see what follows But Just one thing you have to remember what we are assuming here is much much much stronger than P nautical NP It's not only the is the set have no super polo It doesn't have a polynomial time algorithm, but also it doesn't have a better than two to the end run time So two to the end and polynomial. They're very far apart Yeah, it's like it's very very super strong yet somehow it is still believable. It's still possible that two to the end is required So let's see Also, I just want to point out the nice thing about these Reductions implications as you all know is that if I if I have some implication and somehow I get a better algorithm I will refute this and this is very meaningful anyway. So, okay, so Besides these There's three other problems that we have worked on So It doesn't exactly matter what they are, but I would define them What's important is that a lot of different communities have worked on them They're extremely simple and their algorithms are also extremely simple. So here this one here the three some problem it's a problem which is which has Become at the heart of many research papers in computational geometry So you're given n numbers, let's say they're integers and all you want to know if three of the numbers sum to zero and There's various ways to solve this problem in n squared time and squared log n is super easy You just try every pair of numbers and check if the negative of their sum is in the set and the hypothesis here is that Three some requires roughly n squared time There are improved algorithms n squared over log squared of n However, log squared of n is tiny and we don't have an end to the 1.999 time Okay, so this is three some there's another one called orthogonal vectors problem, which again is super simple you're given n Vectors they're very short their dimension is let's say a little bit more than log n and You want to know if the two of these vectors are orthogonal more over these vectors their Entries are either zero one so And the brute force algorithm just tries every pair of vectors confuse the inner product and checks You know is one one of the pairs orthogonal or not This gives you n squared times D Now there is an improved algorithm. This is a little bit hard to parse But basically it says that if the dimension is actually order log n you get a better than n squared Algorithm and to the 1.99 depending on the constant in front of the log n But once the dimension becomes bigger faster growing the log n. This is no longer truly faster than n squared and it motivates this hypothesis that orthogonal vectors requires n squared time essentially now one thing to point out is that Williams in 2005 showed that if you believe the strong exponential time hypothesis for satisfiability Then you should definitely believe this one because you can actually reduce set to orthogonal vectors So that if you have a faster algorithm faster than n squared for set you get a faster than 2 to dn Sorry faster than n squared for orthogonal vectors you get a faster than 2 to dn for set so So this is a really believable hypothesis here In fact, even if set had a faster than 2 to dn algorithm algorithm this hypothesis might still be true So it could actually be very believable Yeah, I mean cnf sat with a linear number of clauses However, actually this if you if you extend this hypothesis to say There's no end to the two minus little of one times poly d time algorithm then actually even full cnf But it's still cnf it's still cnf Yeah, so there are other hypotheses we can we can there are better hypotheses, but in this talk I'll just talk about cnf Good point All right. Finally the third slightly different problem is all pairs shortest paths Classical problem and graph algorithms we teach it study it and so on again. You're given an n-note graph It has weights on its edges Let's say they're even polynomial in n and you want to know for every pair of vertices What is their shortest path of distance? There's like many many different ways to solve this problem in n cube time and is the number of nodes And there's a slightly faster than cube time algorithm like by Williams again And then n cube divided by the exponential of square root log n, but this is still not entered at 2.9999 So there's this hypothesis that has been around in the graphic algorithms community That says all pairs shortest paths requires roughly in cube time and another thing is that these three problems are Central to different communities in computer science this one has been in computational geometry this one in graph algorithms And this one is essentially a set disjointness question if you think about it So it's it appears all over the place. They just basis people care about it a lot for example so, okay, so these are these three other problems and so this answers like what what Are the central problems we care about now you may ask why three? Why don't you just have one? Yes, I'd like to have one. However, there's some research Suggests that if you strengthen strong a th a little bit then there will there's no Deterministic reduction between these three problems. So at least there's some barrier to showing that these are equivalent So it's possible that we need more than one problem to explain the hardness of things Now also if we allow more Hypothesis of course will be able to prove more, but I want to restrict it to have fewer So let's just stick with these All right, so we've covered this And now the most technical part of this talk will be one slide which will talk about what a fine-grained reduction is Yes, this is all for worse case. You can do the same thing for average case But you need to be a little bit more careful. So yeah, I'll get back to it. All right. So let's let's do it So in order to get there Let me remind you of the two main notions of reductions We're used to in NP hardness for example So there's a menu one reduction which essentially says if I have a and b and a is menu one Reducible to be if there's some polynomial time algorithm that takes an instance of a it produces an instance of be a single instance So that the answer of B is exactly the answer to a and a and b are decision problems so this is what a menu one reduction is and Maybe we could do something like this except Paulie and maybe we can put something in there However, this sort of reduction has a variety of weaknesses. So for example, I can't take a Function problem and reduce to a decision problem in this way because just naturally this the answer to be has to be the answer to a and Moreover if I even if I Slightly generalize that if I have a problem like all pair shortest paths where I have n squared answers I have been squared distances. I have to return I can't reduce it to a decision problem by creating a single instance because the single instance just give me one bit Answer and I have to answer. I have to give n squared log n bits in fact So we can't exactly use this and I want to be very general and I have to I want to have Problems that are equivalent no matter what their range of answers are All right, so because of this let's take Turing reductions instead So in Turing reductions now I'm allowed for every instance I run a polynomial time algorithm and I produce many instances of B Okay, and now if I had or a co-access so some magical being gives me answers to the instances of B Then in polynomial time, I solve A So this is a Turing reduction and this is more along the lines of What I want the reason why people don't use it is for technical reasons, right? because it doesn't distinguish between NP and co-NP for example, but For us is better. However, it's still too coarse-grained because it doesn't really care about the running time It just cares about polynomial versus non-pollinome. So what I'm going to do is I'm going to take Turing reductions And I'm going to find make them more fine-grained All right, so here's the notion that we came up with in 2010 so imagine you have two problems A and B and You think that a natural runtime for a is a of n and the natural runtime for B is B of n and I want my reduction to be so that when I take if I had a faster than B of n time algorithm for B Then I would get a faster than A of n algorithm for A. All right, so Let's define it then the reduction I want to have so A and B are problems and a little way and little beer Sometime constructable functions. Okay, there are the run times I say that a is a B reducible to B if for every epsilon There is some delta so epsilon is the advantage you want to have over the B of n time algorithm So then for every epsilon, there's a delta and an a of n to the one minus time delta time algorithm They can solve instances of a of size n by making oracle calls for B. This is the Turing part And here's a picture.  They can have various sizes and one two and sub k And there's this funny condition over here on what their sizes can be and the condition just says That if I had a B event to the one minus epsilon algorithm for B I can run it here on the instances instead of the oracle. I just run the algorithm here and Because the runtime over here will be just the sum of B event on the all of these instances, right? Okay, and this if this is less than a of n to the one minus delta and the reduction time Producing the instances and getting the answer back is a of n to the one minus delta time Then I get an a of n to the one minus delta time algorithm Okay, so this is the definition and two Propositions immediately follow but the first one is that if a is a B reducible to B and B is in B of n to the one minus epsilon time that a is in a of n to the one minus delta time and Also, conversely if I believe a is hard and B is hard as well if a is hard for a event time B is hard for B event time all right Second other nice property is that it's transitive if Is a B reducible to B B is B C reducible to C then a is a C reducible to C They have all there's lots of nice properties you can get out of this and now you can start reducing things to each other now I Want to take a step back now you have this fine-grained notion and Imagine that now I start I I have all these problems in front of me all the problems that you ever care about And I know what their natural run times are and somehow I use this notion to reduce them all to each other There's currently no reason Convincing reason to believe that you can't do that So now you can now have everything be equivalent to each other and really there's only one problem you see and Also, there's only one algorithm. It's the exhaustive search algorithm for that problem So we could live in a world where there's only one algorithm and only one problem and maybe this is how I'll do it You never know Okay, so What we did is we picked some harness hypotheses. We have some notion of reduction and now what can we prove? so What what were people able to prove for sat so well First cook showed that all of NP is reducible to sat and then carp got 21 problems And said that they're all equivalent to set and this Started and be complete All right, and then more stuff happens many many problems were added to this and Also, you can reduce sets and two problems outside of NP. It's a beautiful theory out there now The beginning of our theory is not as pretty so we don't have 21 problems Well, maybe we do I haven't counted but we Counted You are paying attention, you know, he's very smart. Okay, so what's going on here there's There are there indeed only 20 the reason why is the Hamiltonian cycle had two versions undirected injected Very good All right, so Yeah, so what do we know so we have these three problems for if you count that but you know, we have this implication so from the 90s Three some has been shown to imply harness for many problems in geometry they started with a paper by Gadgetton and over Mars in 95 and they said well Let's assume that this simple problem requires quadratic time Can we show that all these other problems also require a quadratic time? and indeed they do and it spawned a lot of Papers on this topic and now many many problems in geometry are known to be hard under the three some hypothesis Recently more recently we started showing that if you believe the three some hypothesis then problems outside of geometry are also hard So you can use some other techniques to also show things about sequence alignment problems and so on over here Orthogonal vectors the set this darkness problem. I mentioned it has many many Implications so soon we soon we started this work We showed we another show like for example longest common subsequence. It requires quadratic time under the orthogonal vectors Hypothesis lots of problems subtree isomorphism graph diameter and so on so it's a very very fruitful hypothesis to start from You get a lot of stuff And one of the interesting things here is all pair shortest paths. We actually have an equivalence class So there's all these problems are actually and cubed and cubed equivalent to all pair shortest paths And you use the full power of fine-grained reductions here So this problem and wide over here is a very simple problem So you're given a graph on n nodes and you have weights on the edges or some integers And I want to know if there's three nodes that form a triangle So there's edges between all three of them and the sum of the weights on the edges is negative Okay, I can easily solve this problem in cubic time. I take every triple of vertices and I check the condition Is it just some negative or not yet? There's this there's nothing better known and in fact if you could solve this decision problem Is there a triangle there then you can compute all the distances all pair-wise distances in the in a graph Very fast. It's very nice and it also kind of led me to believe I don't know if I believe it. Let's put it out there suppose maybe maybe you can take a problem and Maybe the natural algorithm for it is not exhaustive search But it's possible that it's just fine-grained equivalent to some problem whose best algorithm is exhaustive search Just like here all pair shortest paths Think the search space is enormous. There's so many shortest paths out there Okay, exponential number yet. We can solve it in cubic time And they're really the reason is because it's equivalent to this triangle problem and there is actually Cubic number of things a natural in the natural search space, but anyway, I digress let's get back to this So here and also, you know, there's all these problems. They're known to be hard under all three hypotheses There's problems that are not only about static inputs Sometimes the inputs change and you to update the runtime and then you can show tight conditional lower bounds for such problems under One or more more of these hypothesis. So this field is really growing. There's a lot of results out there How what's my time? Okay, good. All right, so And again as I said if you use more hardness assumptions You can prove more but even with these you can prove a lot Alrighty, okay, so now I'll spend the next 10 minutes or less on the conclusion Good so what's the conclusion? Well first besides what I told you about there has been kind of an explosion of research on this and people started applying fine-grained ideas and in Places where it's not really about running time. So sometimes you may care about how much space your algorithms use What is like the trade-off between the approximation and runtime and other stuff? also in different models of computation like IO complexity or Data structures and also there has been a little bit of work on fine-grained cryptography So I'll mention a few things that people have done in this domain so This paper by ball it out They had two papers in 2017 and 2018 and they were concerned with Can we build some cryptographic primitives out of the fine-grained assumptions that we have? Okay, and in particular our assumptions that was pointed out are worse case assumptions so can we get average case assumptions and build crypto out of them and What they did was They developed these techniques where They could get these other problems out of our three things out of all of the autogonal vectors Three some and all pairs of this past they were able to get related algebraic looking problems There are actually hard on average and under nice distributions Okay, and then they were able to get proofs of work from them Which is very nice and the theorems they proved or something of the sort You can generate a challenge is like roughly linear time There is a way to get a proof of work and then to the K time for some small K And then you can check this proof in roughly linear time and every proof must require roughly into the K Okay, so this is very nice, and this is exactly what one cares about Yeah, and so then the question is can you get more out of this? Can you get besides proofs of work? Can we get other cryptographic primitives? Could we get public key encryption and so on from this now? Unfortunately from their approach there is some there are some barriers to even getting one-way functions But it doesn't mean that you can't do it Maybe there's a different way to go about it and get different average case hard problems to get there All right, so then There's another problem, so what if I ask I take my favorite problems of Autogonal vector streets. I'm an old patient is past. Can I show that they themselves are hard on average for some nice distribution? And this would be nice because I don't go to these very messy looking algebraic problems I just I'm stuck. I will be with working with these very simple combinatorial problems that it's easy to work with Unfortunately, it's not too hard to show that for many natural distributions Orthogonal vectors and all pair shortest pass are actually not hard There's much faster algorithms for them on average for example if I take all pressure shortest pass on a graph Where you start with a complete graph and you put weights on the edges which are between 0 and 1 There's some real numbers Then you can compute all pair shortest pass in n squared time, which is optimal because the input size is n squared so also Orthogonal vectors if you Sample your instances by you have some probability p bigger than zero and you sample instances by putting making the coordinates Each each entry is zero with probability p or in one probability one minus P or the other way around and then you can actually show solve that problem into to enter the two minus epsilon time or epsilon depends on p so Yeah Absolutely, I'm saying and in fact, this is great question. There is a nice distribution for and for orthogonal vectors if you assume that sat is hard on average then I do I perform my Reduction to orthogonal vectors and I get a distribution for orthogonal vectors under the assumption of sat is hard on average So there exists some some ways to do it. Yeah Yeah, they're correlated because you have these clauses and so on so they will not look nice Maybe I mean, but we're not start with sat, you know It's I don't know It's a it's a great question This just this all this is saying is that for these very nice distributions. They're easy to solve They could exist some other distributions You can work with very well for which they're not that easy to solve, but we haven't worked We haven't looked at that very closely now what I want to say is that as I mentioned CNF sat and three some They might even be hard for the simple distribution for example three some In fact, I'll show you in the next slide But three some could just be hard by when if you take your integers completely a random from a large enough range Uniformly at random. We still don't know how to solve it faster than in squared time So there's some very simple distributions for which these problems could be So the question is whether these problems are congestion to be hard over finite fields So we're talking of vectors is actually not hard even in the worst case for over random over finite fields You can solve it in sub quadratic time For any finite few Over rings it is hard like over mod six Not rings, whatever Yeah, okay, so Yeah, where was I so you could start working with these two problems even with the simple distributions Of course, we would love to have worst case to average case reductions And this was done recently for a particular version of these problems namely the counting versions So instead of the decision version where you want to know whether There is a three some solution whether orthogonal vectors. There is an orthogonal pair. I want you to count the number This is a much harder problem. Okay, but then you can actually get a worst case to average case reduction In particular gold rack and rough loom did this just recently I think this is a very exciting result And I think this I think this should be true for all these problems that did that the counting version should be hard on average So Good Absolutely for every fixed prime. It's it's solvable and then to the two minus eps one time where epsilon depends on p Sure. Yes If p is very large It's probably hard, but then might as well work with The real version if p is large Good. So This is where we're at now. We don't have very nice worst case to average case reductions for The decision versions very good. So what if I just a third to the there That they're hard on average and then later hopefully prove that they are What does what even what follows? Can we show something interesting that follows? So for example, let's take this problem three some which is related to substance some Okay, but for three some we could make this assumption Which is completely plausible with respect to all we know so what is the assumption? You're given three sets of size n each is drawn uniformly a random from minus n to the d to n to the d Think of these like a hundred And then we say that every sub quadratic time algorithm That's supposed to solve three some of the instances makes a mistake like on half dances Okay, it could be this could be true. We don't have algorithms ruling this out Does this give you anything new in cryptography? So we know that you can build crypto cryptographic primitives from subset some we have these results, but can you also get? ones from three some and This would also be interesting So why not and maybe someday we'll prove this this is fine. I don't know Okay, so in conclusion I mentioned that this field has been growing and I'm really excited to see what's next here I don't know what's gonna come next and I hope you guys can help Thank you. If I believe these I should definitely believe the hardness with me the algebra. Yes I think they're probably much harder actually than these ones Yeah Yes for fine-grained space complexity, so So actually it's a good question. So, you know the three some problem If you consider algorithms that take square root of n space less than square root of n space then Actually turns out that the three some hypothesis is equivalent to the hypothesis that algorithms that take less than square root of n space must take n square time Which is seems more believable, right, but actually it's the same So the question is is there a notion of a shortcut for these problems where if you know the shortcut then you could get a better algorithm so So one thing I can think of is Suppose your input has some special structure, and you know what it is for example if you have a Graph let's say and it has small true and I have the true to treat a composition then I can solve it faster and There's actually So secret a secret, okay Okay, I have to think about it. I think yes. I think the answer is yes, but I have to think about This one We What I need to do is change half to something that depends on on D I Need to change this half over here. You're right. It's a mistake here But this half over here depends should depend on D on how large the things but for D equals three You should be like some constant. Okay, thanks Yeah, oh, yes, okay, so what he's saying is I am talking about this fine-grade notion where you have a function To the one minus epsilon he's saying It doesn't make sense to also talk about improvements in terms of poly logs and terms of the constant factors and so on and yes It does make sense and in fact some of these fine-grade reductions do preserve poly logs in so many instances and You can use this to show very strong hardness So you can show for example that the longest common Subsequence problem if you get a faster than n squared over log to the 10 for example an algorithm then very strange Results in circuit complexity come about so you can you can actually do this but for the purposes of this talk I didn't go into this Yeah Yeah, oh, so I don't remember exactly what the dependence of epsilon on P is I think I'm gonna say the wrong thing probably so it's a polynomial and P But I don't know inverse polynomial, but I don't remember. Maybe it's quadratic. You have to check the paper


So let's dive into the language of statistics. What comes to mind when the typical human thinks of the word population? Lots of people. And does it have to be people? Things, viruses, computers, hard disks, what have you? So a definition like all the things. Yes, that's what's coming to mind. Something like that, the collection of all the items that we're interested in. We've got this emphasis in the same place where you wanted to put it. All the things. Let's shift the emphasis to where it ought to be. Here, the population is what we are interested in for the purpose of making our current decision. In fact, this is going to be a legal contract in statistics. In that sense of the truth, the whole truth and nothing but the truth, the population, the whole population, nothing but the population is what is interesting for your decision. Only the entire population is interesting to you. Anything else but the entire population is by legal contract boring. So please make sure that all your definitions reflect this and that you have carefully and properly specified what is actually interesting to you. So please make sure that you've defined your population to be that thing that is interesting for your decision. Let's make it visual. I love unrealistic examples. All my examples are unrealistic. Here, we have some forest floating on some plains in space. Cool. These trees are our whole population. So we are getting desperately excited about these trees. Any tree that you don't see pictured here, dead to you. This tree right here, boring. It is not your whole population. Only all of them together are interesting to you. What is a sample? A sample is any subset, any sub-collection from our population, like those trees labeled orange or those. Either is a sample. One might be a better sample than the other or both samples. An observation is one single measurement in the sample like this blue one over here.


everyone and welcome once again to another edition of the Red Brun and Williams real estate show. I'm Shannon Deskins with Jennifer Brown Day and Jennifer we're at that point now to where the seasons are changing. We're officially into fall but that has a lot to do with curb appeal because a lot of the leaves are going to be falling and things like that. So what advice can you give to people? It is. It's one of those times a year you know fall the beginning of falls gorgeous. You've got all the change of leaves but then after everything starts dying off it can get a little ugly outside and it also can get to be where you really need to clean up your property for the sake of your property as well. So keeping your gutters cleaned out, making sure that you keep you know the leaves back from your house.  So it's just a really good time to go out kind of do that fall sprucing up and make sure everything looks great for curb appeal. Especially if you have a house listed and we're gonna talk about five properties. I won't say all homes because we've got a couple commercial properties in today's show but let's start with a residential property. Now this is a little farther north than what we normally do. This one's in Louisa. It is. This one is in the Louisa area like you said and it's actually right on the Kentucky West Virginia border. So if you're looking for something in that area it's also very accessible from the Pike County side. If you're going from the South Williamson over towards that way this is also a great way to access that property. Right and this one is a three bedroom two and a half bath home that's sitting on ten acres of property. So space is not going to be an issue. Exactly. This one sits kind of at the end of Sourwood Drive. So that ten acres allows you to have the privacy of kind of being out there by yourself on the end of the road. It has a lock gate that is right there at the entrance so that even more allows even more privacy and then with that acreage you're looking at all that extra space which allows you to have a barn garden space. I haven't been to the property but I've been told that there's plenty of land if you wanted to do any kind of pasture land or anything like that. You know how this area is. This area tends to be a whole lot flatter than what we have up in Pike County. So I'm sure you've got a lot of usable acreage. Now you mentioned great for a barn and garden space but that's included. There is a barn standing on this property and then the established garden space so that is something if you're the outdoorsy type of person if you have horses or you want to get into that kind of thing this one's going to come already ready. Absolutely and then inside the house it is almost 2400 square feet. It's a story and a half kind of a Cape Cod style and it comes with three bedrooms two and a half bathrooms and then you can see in the pictures they did all kinds of that wood detailing so if you like kind of that farmhouse feel this is going to be a great match for you. This one's going to be a great listing. Now this one is actually Kristie Nichols listing. It is and I'm going to give her cell phone number at<PHONE_NUMBER>. And the price on this one not bad 220,000 so this is one you can contact Kristie or call the Pikeville office and you'll be able to schedule a showing for that one. Now moving on to the next couple of ones let's do some commercial properties. This first one is in Floyd County. It is this is in Martin and anybody that's familiar with the Martin area knows where the triangle is. You've got that triangle in the road you've got businesses right there. This is one of those businesses it used to be a dental office so it already has that set up to it dental medical anything along those lines this is going to be a great building for you. You've got your exam rooms you've got your waiting room you've got all the different aspects that you would have to figure out how to set up for this office already ready. Already ready and already ready in a known commercial area so you sit right there close to a bunch of the banks and that kind of stuff in that triangle really close to where McDonald's is right off of round 80 so it's in a great area to establish a business that's already in an established area. Right it's almost 2,500 square feet so it's a good size as far as that looking at the picture of the front you can see it's got adequate room for parking and things like that and those are things you need to think about when you're looking at a commercial piece of property. Absolutely and then the other thing to take into account is the current owner has gone in and spent some money and done some updates so you have a newer roof newer hot water heater new heating and air units flooring new drop ceiling so hopefully this is one you can go in kind of put your personal stamp on it but it's already ready for business. The price on this one 229,000 now Jennifer this is one that you're handling right? Actually this is one out of our Pikeville office that Beverly Newman is handling he's one of our new agents. Okay so let's give some information so we can get ahold of Beverly let's give her email address. Okay her email is bnewman at rbnw.com. All right now moving along we'll stay on the commercial side of things but we'll move actually into Pike County with this one this one's at Coal Run. It is this is a bank old bank building at Coal Run that's kind of how everybody's gonna know it but it says right on 23 has adequate square footage to be another bank or about any business that you would want to put in. I know you're looking at over right at 3,600 square feet but this one like you said is set up for a bank so you've got your drive-thru lines you've got the window you've got your front lobby but like you said there are a lot of different businesses that could utilize a drive-thru space or enclose that I think we talked about that once before. We did where you've already got the roof line for that drive-thru space you have the ability to almost double the size of the building if you would want to enclose that portion as well so that's something obviously that would come at a fairly large cost but it's something that if you're looking for something that's closer to the six seven thousand square feet that would be an option. It's been recently a bank five private offices a boardroom two half baths four tailor stalls and then a large kitchen and storage space so this is one that you could easily go in you could make a few adjustments if you wanted to open up a bank or like we said if you wanted to do another type of business you pretty much have an open floor plan with those offices being around the perimeter wall so you can easily change it around or do whatever you'd need to. We're forgetting to mention this is in Coal Run right on US 23 as far as location goes it doesn't get much better as far as traffic and the people that are going to be exposed to your property. Exactly this is in a very high traffic area for Pot County so this is something if you're looking to have that drive-by traffic if you're looking to have that sign directly on US 23 this is a great option. This is one like we said if you're looking at you know banking or anything that would would use those drive-thru stalls or anything kind of put your mind around that the list this one is listed for 875,000 so this one is another one out of your Pikeville office. It is this one is actually mine and my Pikeville office number is<PHONE_NUMBER>. Alright just give Jennifer a call she'll be able to to get you down there and walk you through that property. Now moving on this one we've got one of the next two the last two we're gonna talk about just went through some big price reductions so that's gonna be attractive. They did and both of the sellers are motivated to hopefully get some offer so these are ones that we wanted to mention throw out if you have an interest in either of these next two properties they're ones to really take into account right now. The first one we'll talk about is not far from the bank building we just talked about at Coal Run. This one is on Joe Stanley Road now this is one half of a duplex. Correct it is one half of a duplex like you said it sits just down from that last listing so you're up on the hill right there in Coal Run directly off US 23 and this is one the current owners have gone in and done some amazing updates to it it is completely moving ready if you're looking to downsize if you're looking for something that's very low maintenance this is a great property. And that would be for let's say you know the kids are now in college and this is a time of year when it's starting to sink in that wow we're empty nesters you know we can downsize now or if you travel a lot this is one like you said low maintenance is the key for this one. Exactly it's a two bedroom one and a half bath in that one and a half bathroom they have completely new bathrooms new vanities new fixtures everything is brand new they went into the kitchen did custom kitchen cabinets they put in quartz countertops stainless steel appliances and then throughout the house it's new lighting new doors new windows everything has been changed out and then you've got on the outside a private back deck you can put a grill you can do some outdoor dining areas maybe even a hot tub at some point so this one is going to be attractive to a lot of people who are looking for maybe a smaller place but all the new updates. Yes and that's what this one offers and like we said very low maintenance yes you have that back deck but you have a very small amount of grass to mow it's probably one of those that you can go out with your little push mower that's not even gas powered and get it done real quick this is something that you can go out you have enough to do to play outside and kind of sit outside but you're going to have very low maintenance you know for those weekends. And the price on this one at 124.9 this may be something for an investment property if maybe you have rentals or you have properties that you lease or rent out this could be something that you could purchase to do that for extra income in the long run. Absolutely this would make a great rental property if somebody is looking for additional income this would be one that would be great to get into. And as we mentioned at the very beginning of this listing this has been reduced it is now 124.9 so the price is going to be attractive whether you're going to buy it to live there yourself or maybe you're looking at using it for some rental property. So let's give your email address on this one. Okay the email is Jay Brown at rbnw.com. All right now we'll end the show with another piece of property that the price has just been reduced on and this one is actually in downtown Pikeville. It is this one is directly off Myra Barnes which runs parallel to Handley Boulevard over in that residential areas you're coming into town and this is one like I said super convenient because of the location but it's another very low maintenance home. Right now this one is a ranch home that kind of like you said everything is kind of when you go into the house as you go deeper into the house it just keeps unfolding. Exactly it has four bedrooms two full baths the layout is great for a growing family because you've got three bedrooms up front one of the master bedrooms is in the back so that's a very easy layout for families as well. And I love the the updates and the extras that this one has you've got the hardwood flooring you've got a sunroom you've got a bar space if you like to entertain and that's you've got your family room your master bedroom and all of these things are in a layout that's great for entertaining. Exactly and then one of the great things sometimes in the city it doesn't come with off-street parking this one actually has a lot of off-street parking you can fit about two to three cars and then you of course have the street parking for additional but it's great to have that as well.  Exactly and if you're a big hillbilly days fan this would be a great location to walk in for hillbilly days or anything like that as well. But like you said four bedrooms two bathrooms almost 2400 square feet so you've got a lot of space with this one. You do you have a lot of space you have a lot of space on the outside but like I said very low maintenance small little garden area a really nice covered front porch so this is one that has both of them. I love the front porch you got that outdoor space too as well so this is one that as we mentioned the price has just been reduced as well this one is now 214 but like we said you're getting all that in downtown Pikeville right off Hambly Boulevard so I think this one's going to be attractive as well. I hope so and if anybody would want want to see it please give us a call in the Parkville office<PHONE_NUMBER>. And of course there's a red runner Williams you sign in the front yard feel free to do that that drive by. Absolutely. All right now we've talked about a lot of things that are listed but now we're gonna tell you or Jennifer's gonna tell you why it is important to hire a realtor whether you're buying or you're selling. Why use a realtor? Using a realtor to buy or sell real estate has many benefits. First your realtor is familiar with the market familiar with competitive and comparable properties and can help you either price your property effectively for a sale or make a competitive offer on a house that you hope to purchase. Second your realtor can help you navigate the home buying or selling process from start to closing. The home buying and selling process can be stressful and time-consuming and using a professional will help you get through each hurdle more efficiently. The realtors of red runner Williams real estate services will be honored to assist you through the buying or selling process. Please give one of our four offices a call to speak to one of our agents. Thank you for joining us for the red runner Williams real estate show. We hope to see you again soon.


Here is one activity that I use to teach my students for counting forward during the day. Once the children have reached and are capable of counting by 1s, 5s, and 10s, I move on to this activity. It is the exact same activity that we did during counting by 5s and counting by 10s. We are going to play count and sit. The difference this time is that I am going to tell the boys and girls a mystery number. And I am going to tell them what number to start counting with. For example, we are all standing up and I would say our target number or our mystery number is 25. And I am going to start with the number 6. So I say 6, the person next to me says 7, 8, 9, and so forth until the child says 25. The child that says 25 sits down. And I have a new mystery number, my mystery number this time might be 53. And this time I might have the child that is next to the person that is sitting start with the number 12. And we will go 12, 13, 14, and so on until we get to 53 and that child sits down. Now if I am going to use higher numbers like 93 or 87, I am going to start higher. So if my mystery number is 87, I might have the child start with 66 to work their way up to that. We will continue this pattern until everyone in the class is sitting down because they have hit the mystery number. You can practice this in a circle. You can practice the standing in line waiting to go to the cafeteria. You can practice this anywhere where you have some extra time that you need to fill. This is an activity that I use to help my students count forward.