MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams

Ryan Williams is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I interviewed him all about his work starting by asking him a popular Leetcode question (3 SUM). Correction: In this podcast I say "lower bound" when I mean "upper bound" and vice versa. Was speaking using the intuition that lower is better for running time. In reality, the accurate usage is: "Lower bound" = A proven floor for a problem e.g. "no algorithm can possibly be faster" "Upper bound" = A proven ceiling for a specific solution e.g. "there exists an algorithm this fast" Professor Williams answers as if I spoke accurately so the error didn't impact the flow of conversation. Just a correction for the record • My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/ • The Kickstarter page for it: https://www.kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done Podcast links: • YouTube: https://youtu.be/AaK1SL2i_4Y • Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835 • Transcript: https://www.developing.dev/p/mit-complexity-theorist-on-leetcode Thank you to this episode's sponsor for supporting my work: • WorkOS: makes your app Enterprise Ready with easy to use APIs to add SSO, SCIM, RBAC, and more in just a few lines of code, check them out at https://workos.com/ Timestamps: (00:00) Intro (00:41) Asking him a popular Leetcode question (03:54) Doing better than the popular optimal solution (08:26) Fine grained complexity (17:00) A severe strengthening of P vs NP (24:38) SAT problems and solvers (34:51) Hot takes on famous open questions (46:57) Simulating space with time (01:01:02) Why he solves hard problems (01:02:35) How to pick good research direction (01:07:14) Technical book recommendations (01:08:31) Advice for his younger self (01:11:56) Outro Where to find Ryan: • Wikipedia: https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist) • Website: https://people.csail.mit.edu/rrw/ • LinkedIn: https://www.linkedin.com/in/r-ryan-williams-a1b534a/ • X/Twitter: https://twitter.com/rrwilliams Where to find Ryan: • Newsletter: https://www.developing.dev/ • X/Twitter: https://x.com/ryanlpeterman • LinkedIn: https://www.linkedin.com/in/ryanlpeterman/ • Threads: https://www.threads.com/@ryanlpeterman • Instagram: https://www.instagram.com/ryanlpeterman • TikTok: https://www.tiktok.com/@ryanlpeterman Referenced in this episode: • Some Estimated Likelihoods for Computational Complexity: https://people.csail.mit.edu/rrw/likelihoods.pdf • Simulating Time with Square-Root Space: https://arxiv.org/abs/2502.17779 • Cook and Mertz's tree evaluation paper: https://dl.acm.org/doi/10.1145/3618260.3649664

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Speaker 00

  Hypotheses which are at the edge of our understanding can be enlightening.

• 0:04Ryan Peterman?

  This is Ryan Williams. He's a professor at MIT who won the Gödel Prize for Theoretical Computer Science. And I started by asking him a Leet code question. So the question is threesome. Can you do better than n squared for this?

• 0:18Speaker 00

  Yeah, you actually can do better than n squared. And this is not at all obvious.

• 0:23Ryan Peterman?

  He also had contrarian takes on popular hypotheses.

• 0:27Speaker 00

  I think I'm on the record as not believing this hypothesis. We really don't understand polynomial time computation as deeply as we think we do.

• 0:42Ryan Peterman?

  All right, I want to start by asking you the most popular Leet code question. So the question is threesome. Given a list of numbers and we want to find three numbers such that they sum to zero.

• 0:57Speaker 00

  Yes.

• 0:58Ryan Peterman?

  And so what are your thoughts on the brute force solution for this? We can start there.

• 1:04Speaker 00

  So the obvious brute force solution takes, if you've got n numbers, n cubed time. Just try all the triples of numbers, sum them up, see if they sum to zero. There is a faster solution. So one way to get an order n squared time algorithm for threesome is to first start by sorting the numbers. And then you go through the numbers one by one. Say like you're looking at a number a. And you want to know, is there a b and a c in the rest of the list? Whose sum with a is going to be zero.

• 1:45Speaker 00

  Okay, so the way this works is after you sort the numbers, you do what's called a finger search. So you put the finger from your left hand on the minimum element and a finger from your right hand on the maximum element. So you start there and you check like, okay, are these my b and c? Right, so you add them min and max and check if adding that with a gets you zero. Okay? And if you're lucky, okay, then you're done. But typically, you're not lucky. And so this sum of the min and the max is either

• 2:27Speaker 00

  larger than your target value minus a, or it's smaller. Okay, if it's larger, then you need to decrease the larger number. So you take your right finger, which is sitting on the maximum element, and you move it to the left one slot. Okay, so you decrease the larger one. All right, if the sum is smaller than your target, you need to take the smaller number and make it a little bit bigger. So you move the, you move your left finger, sitting on the minimum, over one slot. Okay, and you, you keep doing this. You keep checking whether, you know, your left finger and right finger are pointing at a solution. And if they aren't, then you adjust it.

• 3:09Speaker 00

  If they do, if they ever do sum up to exactly what you want, you're done. And so after each comparison like this, right, one of your fingers moved. Okay, if the fingers ever cross, then you don't have a solution. Like, there's just, there just can't be a solution. And so the number of times you move, you know, your fingers in total is like n. So, so you have an order n solution for finding that extra pair. And you do this for each of the numbers a. Okay, so then you get an order n squared solution overall. You do it n times. Each finger search takes order n time.

• 3:50Ryan Peterman?

  And that is the popular solution.

• 3:53Speaker 00

  That's the popular solution.

• 3:54Ryan Peterman?

  A lot of people know when we're in these algorithmic leaked code interviews. And I know a lot of your research is kind of about pushing lower bounds. So maybe we can

• 4:05Speaker 00

  Yeah.

• 4:06Ryan Peterman?

  start that conversation off by can you do better than n squared for this?

• 4:10Speaker 00

  Yeah, you actually can do better than n squared. And this is Not at all obvious. In fact, it stems from taking this finger search idea and pushing it in a different direction. So what you do is you take your sorted list, okay? And you break the sorted list up into little groups of contiguous elements. So let's say your little group is like log n size or square root log n. It's like a really small little group, okay? So you've got either n over log n groups total or n over square root log n groups total, depending on how you break up your groups.

• 4:51Speaker 00

  And then the idea is you're going to perform the same kind of finger search, but you're going to set things up so that you're comparing two pairs of groups. Your finger is always pointing at an entire group. So like the left hand and right hand are pointing at two groups. And you want to know if there's a threesome solution in that group. And you can set up a kind of fast data structure to check a small group. Okay, this data structure will take much less than the number of elements in the two groups squared. So you set up some kind of fancy data structure. And because you set your group size so small, it's like a preprocessing that you do

• 5:35Speaker 00

  over all the possible inputs you could send from a pair of groups. And so you have some data structure and it will, you know, let's say it takes you into the 1.5 time to prepare this data structure, this fancy data structure. But now, when you're looking at a pair of groups, you can look up the answer much faster than what finger search would have taken. I guess finger search through like a group of length g and another group of length g would take about order g time. And you can do, actually do faster by this kind of lookup, this kind of table lookup. I think it is kind of like you, you take uh this list of length n

• 6:15Speaker 00

  and you uh kind of shrink it into like n over num, n over, n over group size uh number of things and these are more complicated objects. And then you do, and now like you, you're trying to, you're trying to speed up like the check over these like small uh complicated objects for like, should I move my finger to the right? Now, is there nothing in this group? Would finger search just, just go straight through this group or not? Is basically what you're asking.

• 6:45Ryan Peterman?

  So the unit that you're operating on is not a single integer, it's a, a group?

• 6:49Speaker 00

  Yeah, it's like a group of them. So you use some kind of table lookup. Uh, and so, well, it's, it's, it's much fancier than a table lookup, actually. It's, it goes through some other model called the linear decision tree model. Like, so it's like in some weird model where you can actually get a faster threesome solution. You can get into the 1.5 solution. It's a really interesting and sophisticated solution, but what I want to emphasize is that it starts from the finger search solution and sort of like figuring out how to like process finger moves faster. Uh, so do pre-processing so that finger moves can, can go faster.

• 7:26Ryan Peterman?

  Yeah, I saw the, the time complexity of this. It's n squared divided by log n divided by log log n all raised to the two thirds. What, is there any intuition behind, I mean, that's just crazy.

• 7:40Speaker 00

  So there are several algorithms of this kind and they all work by doing some modification on what I was talking about because you can sort of reduce to a different model. Like a, like a, a, a different kind of lookup table, a different kind of set of tricks. And you know, maybe there are some savings you can do here and there by sort of compressing things a little differently. Um, so that, yeah, there are several algorithms that beat the n squared running time bound. And they all, to my knowledge, kind of work in a similar type of, of way. Like they, they're, they're taking this in squared time algorithm, finding little ways to like

• 8:18Speaker 00

  pre-process and then optimize like based on the pre-processing, like make finger searches faster and things like this. Sort of, yeah.

• 8:27Ryan Peterman?

  A lot of your research is on this topic of fine-grained complexity or kind of lowering lower bounds, so maybe you can explain what is

• 8:37Speaker 00

  Lowering lower bounds, I like that.

• 8:39Ryan Peterman?

  Yeah.

• 8:40Speaker 00

  The idea behind fine-grained complexity is we have a variety of problems, canonical problems that we teach to undergrads, we have canonical algorithms for these problems. These algorithms have resisted any major improvements in decades, and so we wonder, are these algorithms optimal? And what does a theory of optimality look like in terms of time complexity? So what if we just focus solely on the time complexity of a problem, like the fastest algorithm that will solve that problem?

• 9:22Speaker 00

  What does complexity look like then? Because like P versus NP is not about time, I mean, it's about time complexity, but on a coarse-grained level, where P is just polynomial time, or that polynomial could be n to the 10, n to the billion, whatever, and so like showing that something's not NP is showing that it needs some super polynomial amount of time. Whereas here, we are concerned with, there's a canonical problem, it takes n-cube time with some very elegant canonical algorithm. We want to know, could you do any better? Could you improve that exponent to n to the 3 minus epsilon, for some epsilon?

• 10:06Speaker 00

  And then you ask, well, suppose I have a problem over here, and it has a quadratic time algorithm, and I want to know if I can improve that quadratic time algorithm by a little bit? So then you start asking questions like, well, suppose I improve this algorithm by a little bit? Can I improve this algorithm over here by a little bit? And this is naturally a notion of reduction, like saying that like, I want to have some reduction from problem A to problem B. So that if I can improve the algorithm for problem B just a little bit, then I can also improve the algorithm for problem A, but just a little bit. This actually leads to a different notion of complexity.

• 10:51Speaker 00

  You can even take an NP-complete problem and a P problem, and reduce the NP problem to the P problem, and the question still makes sense. So, for example, you could talk about the subset sum problem, okay? So the subset sum problem, you've got n numbers and a target value. And you want to know if there's a subset of those numbers that sum to a particular target value, okay? Now, you've got n numbers, there's 2 to the n possible subsets. The obvious algorithm takes 2 to the n time, okay?

• 11:32Speaker 00

  But you can actually do better than this. And the way you do better than this is to reduce to a polynomial time solvable problem.

• 11:41Speaker 00

  So you can get an algorithm which runs in square root of 2 to the n time for the subset sum problem. You can avoid enumerating over all the possible subsets in a substantial way. And this is in fact known commonly in cryptanalysis by, I guess, like a meet-in-the-middle type of approach. Like, so people do this sort of thing all the time. The idea is you partition the set of all the numbers into two halves, n over 2, n over 2. You enumerate all the subset sums on the two halves. So you have 2 to the n over 2 possible sums for like the first half,

• 12:25Speaker 00

  2 to the n over 2 possible sums for the second half. Then you want to know, is there a number from the first half, you know, from this huge list? Plus another number from the second half. This huge list that sums to the target. Now, this is the two sum problem. This is really nothing more than a two sum problem, which you can solve by sorting and binary search. And this is a reduction. We have shown how to solve a subset sum problem, like which would normally take 2 to the n time in square root of 2 to the n time. An NP complete problem. By reducing it to a problem like two sum.

• 13:08Speaker 00

  The obvious algorithm there takes in squared time, trying all the pairs of numbers to see if they sum to a target and using an n log n time algorithm for that. So, so fine-grained complexity can, can relate problems that would not be relatable at all in the traditional P versus NP theory. Like, one problem is NP complete, the other problem's not. So they, they should not have a polynomial time reduction between them. Like in general, right? But so, but if you just look at the time complexity and you focus on, okay, I have an algorithm, 2 to the n algorithm, is it the best possible? Then, um, and then I have an n squared algorithm, is it the best possible? And you, then you can relate the two problems. And this is a general phenomenon that you can relate

• 13:54Speaker 00

  problems that look like they should have nothing to do with each other.

• 13:58Ryan Peterman?

  So you talked about, you talked about reducing subset sum to two sum. And, but subset sum is n arbitrary integers that sum to the target sum, right?

• 14:11Speaker 00

  Yeah, so the idea is, um, nobody said I had to use a polynomial time reduction or something like that to reduce one problem to another. So, so what's, what happened? What happened? The trick was, I took this subset sum problem that had n numbers. And then I blew it up to an instance of this two sum problem. But that two sum problem has about square root of 2 to the n numbers.

• 14:40Speaker 00

  Now, I can solve two sum in linear time. So that, so solving that instance gives me a square root of two in time algorithm for the original problem. But yeah, in, in the meantime, going from one problem to the other, I blew it up. But by blowing it up, I'm able to improve the time complexity of the obvious algorithm for subset sum.

• 15:02Ryan Peterman?

  I get it. Okay, so the reduction, it's kind of like the, if you solve the subset sum, you have some time complexity. If you translate it to the other problem, you lose a little bit of time complexity, but less than the aggregate.

• 15:17Speaker 00

  So all you want to make sure is when all the dust is cleared and settled, you want to be able to say, look, if I can improve the obvious algorithm for two sum, then I can improve the obvious algorithm for subset sum. And that's what this thing achieves. Because I know, because I know how to get a faster algorithm for two sum, I can get one for subset sum. So, so you just want your, your reduction between two problems to have this property. If I can improve one problem by a little bit in running time, I can improve the other problem by a little bit.

• 15:50Ryan Peterman?

  In one of your talks, you, you mentioned preserving magic between.

• 15:54Speaker 00

  Right.

• 15:54Ryan Peterman?

  Okay, so this is that.

• 15:55Speaker 00

  Yes, this is exactly like preserving magic because, well, I mean, once you see the two sum solution, it's not so magical anymore. But imagine that you didn't know about sorting and binary search and the like, and someone just says, find a pair of things with a certain property, and there are n things. And you're like, well, I mean, all, the number of possible pairs is about n squared, so maybe it'll take me n squared. In this particular case, because they're numbers and you're summing them, there's an n log n time algorithm. It is a, it is a surprise when you first see that, no, you don't have to try all of the pairs of numbers. There is a shortcut.

• 16:39Speaker 00

  There is a clear shortcut that, that you find a pair much faster. And then you can use that surprise or magic, if you will, and get something for a subset sum, get an algorithm for a subset sum that avoids trying all of the to the end subsets.

• 17:00Ryan Peterman?

  So I understand one of the the driving motives for pursuing this, I guess, lowering of lower bounds is that strong exponential time hypothesis, I see it, you know, SETH. Could you explain that and its significance?

• 17:18Speaker 00

  Strong ETH is like a severe strengthening of the P versus ZMP question. So P versus ZMP is asking whether the SAT problem

• 17:34Speaker 00

  has a polynomial time algorithm or not, right? And strong ETH is basically saying that for the SAT problem, you cannot solve it faster than, much faster than to the end. So there's no 1.999 to the end time algorithm. For every string of nines, there is no 1.9999 to the end time algorithm.

• 18:05Speaker 00

  To say the hypothesis totally precisely, it has to do with the K SAT problem. And you're looking at clauses of length k for arbitrary k. But those details don't matter so much. It's a canonical NP complete problem. SAT is solved all the time in practice. It's extremely useful for verification nowadays. It's an it's an engine for verification. So it can be solved fairly well in practice. However, in the worst case, we still don't know how to solve it significantly faster than to the end.

• 18:49Speaker 00

  So the hypothesis that it needs, say, 1.99999 to the end time for all strings of nines is a very strong exponential time hypothesis. It was stronger than P different from NP. It says, no, no, no, it's not super polynomial. It's actually darn near to the end time that you need.

• 19:09Ryan Peterman?

  Right. And so do you think that hypothesis is true? And, you know, why or why not?

• 19:15Speaker 00

  I think I'm on the record as not believing this hypothesis. Yeah.

• 19:22Speaker 00

  You know, why don't I believe this hypothesis?

• 19:26Speaker 00

  Well, I started thinking about this hypothesis. Maybe already as an undergrad, but certainly starting in grad school. Like early in grad school, I was thinking about this. So before it was even called Strong ETH, I guess that shows how old I am. I was trying to think about how to solve the so-called C N F SAT problem faster than to the end. And, well, at the time, there were a number of other NP complete problems that had faster algorithms, like subset sum. So I thought, well, there's not, I mean, what's so special about SAT?

• 20:08Speaker 00

  Like if all these other problems have faster algorithms, why not SAT as well? Like if you restrict to the three set problem, like, so this is where you have an AND of these clauses. Each clause has like, is an or of three variables. Some of the variables may be negated. You want to know if there's a way to set all the variables to make all the clauses simultaneously true. There is a faster algorithm for that, but this is a more general version of SAT.

• 20:45Speaker 00

  So at first I just thought, well, there's no good reason to think in a lower bound, these other related problems have upper bounds, so why not? But then, over time, I would have different attacks on Strong ETH, like trying to refute it, always trying to refute it in different ways. These attacks would fail. In some completely catastrophic and ridiculous way, like they were like have no chance of actually solving the original problem. But by sort of staring at my failure and trying to think, well, there's something interesting happening here. What can I do with this?

• 21:29Speaker 00

  Like, there's something interesting. Yeah, it doesn't refute the strong ETH thing. What does it do? So by trying to pivot and figure out, okay, what can I do with my failure? I was able to solve like a variety of other problems instead. And so after a while, I realized that the truth value of strong ETH to me is almost irrelevant. Like, because if I believe that it's false, then I get good ideas. I get, I get good ideas, like, and so by trying to think about, okay, what would an algorithm that breaks to the end look like?

• 22:13Speaker 00

  What could it look like? I, I sort of forced myself to think in a different way. I, I have to like discard other natural algorithmic possibilities because we know they, they won't work. And I had to think in a, in a different direction. And so because it kind of like sends my brain in a different direction, sends me thinking a different way, it's very useful for research. You know, I mean, even, even though I still haven't refuted it or whatever, like it's very useful for me to believe that it's false, like operationally. So the truth value, I mean.

• 22:55Ryan Peterman?

  I believe this is a minority opinion, right? Why would they go against?

• 23:00Speaker 00

  I mean, I think. For example, Russell Impaliaso, a good friend of mine who helped propose this. I mean, he always emphasizes to me, well, this is a hypothesis. You know, we explicitly did not name it a conjecture. We wanted to sort of put forth some lower bound that would get you to think about it. Like something that's maybe a little more controversial than the other types of things like P M for M P or whatever, or you know, like other things that people more normally believe. So like hypotheses, which are at the edge of our understanding can be enlightening to

• 23:40Speaker 00

  think about, like where we truly don't know what the answer might be based on our intuition. So this is, I guess, one reason why it was proposed, but one reason why you might believe that strong teenage is true is because believing it implies a lot of other lower bounds for you conveniently, because you can reduce the SAT problem to a bunch of other problems that seem totally unrelated, like edit distance, various pattern matching problems. They have natural polynomial time solutions.

• 24:21Speaker 00

  If you can improve on the algorithms for any of those, you would improve the one for SAT as well. You would get something better than to the end. So believing in it sort of makes a convenient worldview. It shows that all these different textbook algorithms are indeed optimal.

• 24:38Ryan Peterman?

  We've talked about SAT or we've mentioned SAT so many times in this conversation. I know there's so many forms of that problem. What are all the different forms? And I know there's clause width, also this idea of depth too.

• 24:52Speaker 00

  The most common. Representation of a SAT formula is a conjunctive normal form, so-called CNF representation. And this is what modern SAT solvers get as input. They get their file in so-called Dymax CNF form. And this is just every line of my file, I give you a list of variables, possibly with negations, and each one is a clause. And I'm supposed to take the or of those variables or negations. These are variables or negations are often called literals. Okay, so I take an or of these literals.

• 25:34Speaker 00

  And the width of that clause is the number of literals in it. Okay? And I'm supposed to take the and over all those lines, each line in my Dymax CNF file. And so it's an and of a bunch of ors, and each or has some small number of literals in it. Call it k. So usually the width is called k. And so the kSAT problem is to find an assignment to all the variables that satisfies all the clauses when each clause has width k, or width at most k. It could be smaller.

• 26:17Speaker 00

  So that's the most popular version. That's what SAT solvers, you know, churn on. And that's what is behind strong ETH. That's the representation there. But there are other ways to represent a Boolean formula. You could just simply represent it as some arbitrary expression made up of ors and ands and negations. It could just be some arbitrary expression with nested parentheses and all that mess. You could ask, you know, given a formula and this representation with a bunch of variables, is there a way to set the variables to make this true? That's formula SAT.

• 27:01Speaker 00

  You could also look at

• 27:06Speaker 00

  at circuits of bounded depth, as you mentioned. So there is this

• 27:13Speaker 00

  class of circuits that people study called AC circuits for alternating circuits. It doesn't mean alternation in terms of electricity. It means alternation in terms of ors and ands. So these circuits are made up of ors and ands, like in layers. So the CNF representation is a special case where I have an and of ors, like like an and of a bunch of clauses and an ors of the literals. But you can go further. You can have an and of or of ands of variables with negations and things like that. And so these are constant depth AC circuits.

• 27:58Speaker 00

  And because the idea is you only have some constant number of layers of these ands and ors. And you can look at the SAT problem on circuits like that as well, for example. Those are, those are two other versions that people look at.

• 28:13Ryan Peterman?

  Yeah, Strong ETH is on kSAT. And I saw on less than, or I guess, you know, two SAT, three SAT, four SAT, five SAT. There exists solutions that are asymptotically better than two to the N. So I guess it, it, you know, the larger K can be, the more difficult.

• 28:33Speaker 00

  Yes, that's the intuition. That, that is the intuition.

• 28:36Ryan Peterman?

  Okay, have you ever plotted that curve? Like, is it, does it drop off, you know, exponentially or?

• 28:41Speaker 00

  Yeah, yeah. Yeah, that's what's so interesting about the current state of the art in kSAT algorithms. As K increases. All of them, all of the different types of algorithms you might try to run, they all approach a to the n exponent. Like as k grows and grows and grows, they get 1.99, 1.999, and so on. And yeah, it drops, I mean, it gets, in other words, it goes towards two pretty quickly, actually. And like, so we understand like how the exponent behaves pretty well for the known algorithms we have.

• 29:24Ryan Peterman?

  And then for for something like three set, what is the intuition behind speeding up an exponential time search?

• 29:32Speaker 00

  Yeah, so for three set, um, let's just look at a single clause, okay? A clause that's got three variables in it, okay? We know that if, uh, if we set all those three variables wrong, it's going to be false. Okay, so we have to avoid one of those assignments, okay? Well, that means that there are seven out of the eight possible assignments. So there's like three variables to the three, eight possible assignments. Seven of them could be a satisfying assignment. They could be part of a satisfying assignment, we don't know. But one of them is definitely not. So the one easy way to see that two set can be solved in less than two the end time

• 30:16Speaker 00

  is just take any clause, try one of the seven possible assignments, and plug them in, and then recurse on the remaining formula. Now, let's think about what we did. If we were just trying all the possible to the end assignments, and we we would like plug in, you know, uh, one of eight possible assignments for each of those three variables. And so we'd have eight recursive calls. Well, instead, because we're clever and we looked at the clause, we have seven recursive calls. And that that's the difference. So so we reduced, uh, by three variables at the cost of seven recursive calls as opposed to eight.

• 31:02Speaker 00

  And this gets you a slight improvement. This gets you about 1.92 to the N. Something slightly better than than to the N. Okay, but you can do better than this. But this is this is sort of like the idea. You try to look at ways to plug in variables that will force constraints. So you can rule out a large portion of the possible assignments.

• 31:30Ryan Peterman?

  When I was thinking about circuits and, you know, the different widths and depths. I don't know if this is a unusual question, but it it reminds me of neural nets. But the operators are different and the space of the the literals is different. So instead of booleans, it's maybe floating points. And so it just made me wonder about the algorithms that you might apply on a neural net. Is there, you know, analogues in between these two spaces?

• 32:01Speaker 00

  Yes, yes. So, um, yeah, if we look at, say, I want to model a neural network on. So I want to compute, say, it's still a Boolean function. But I want to do it with like a neural network. So like I want to use, let's say, ReLUs or sign activation functions or what have you. There is a slightly more general like gate that we can use instead of ors and ands. That turns out to basically be equivalent. So if instead of using ors and ands, we use a so called majority gate,

• 32:45Speaker 00

  which outputs one if and only if at least half of its inputs are one. Using this and negations, we can actually simulate neural nets, like the usual types of neural nets that you think of with the usual types of activation functions. So if they have a constant number of layers of neurons, we can get a constant number of layers of majority gates and and negations. So once you go, so this is so called TC circuits for threshold circuits. Yeah, so once you allow threshold circuits, you can start to model neural networks.

• 33:24Ryan Peterman?

  Still using booleans.

• 33:25Speaker 00

  We're still looking at boolean inputs, though, yes. So, once you allow your input space to be larger and like have floating points, then you can prove a lot more in terms of lower bounds. You can find like things that take like depth 3 in a neural net that can't be done in depth 2 and so on.

• 33:52Speaker 00

  So, yeah, once you go past that and you start looking at just arbitrary real domain, it becomes a totally different picture from a discrete domain.

• 34:04Ryan Peterman?

  OpenAI, Anthropic, Cursor and Vercel all use this product to make their lives better. And the problem it solves is when you're building SaaS or an AI product and you want to sell to other companies, there's all these requirements you need to meet. There's SSO, there's SCIM, there's RBAC, there's audit logs. These are all things that take time to integrate but aren't the main focus of your app. WorkOS is an API layer that lets you meet all of these requirements in just a few lines of code. So let's say you have a new SaaS product and you want to sell to other companies. WorkOS will solve all of these critical feature gaps for you. You can check them out at workos.com to learn more and get started. And I appreciate them for supporting my work

• 34:49Ryan Peterman?

  and sponsoring this podcast. One topic I thought might be fun to go over is you wrote this paper about the likelihoods of these various conjectures in complexity theory. And I polled a few of these that were kind of minority opinions or maybe, you know, less common takes.

• 35:08Speaker 00

  Sure, okay.

• 35:09Ryan Peterman?

  Curious to hear your rationale.

• 35:10Speaker 00

  Okay, okay.

• 35:12Ryan Peterman?

  One of them, the well-known one, you know, P not equal to NP or you know, P versus NP.

• 35:20Ryan Peterman?

  You assigned an 80% confidence that they're not the same.

• 35:24Speaker 00

  Yes.

• 35:24Ryan Peterman?

  And I think most people say much higher confidence. So why would you assign such a low confidence that they're not the same?

• 35:32Speaker 00

  It's interesting because I think I originally had something like 75%, but then my college classmate Scott Aronson was like, "How dare you?" kind of. He was, he sort of called me out. I'm like, "Okay, fine. For you, 80%, fine." I guess my point is that we really don't understand polynomial time computation as deeply as we think we do. And there are surprises, like all the time, in the power of algorithms. There are very few surprises in terms of lower bounds. Like, when we are able to prove a lower bound,

• 36:17Speaker 00

  typically, it's something we very much expected to be true, but it was hard to prove. It was hard to prove. Somehow, we pulled it off. We got what we expected to be true. But all the time in algorithms, people are finding algorithms where it's just like surprising, just, "Wait, what? How, how do you get something that fast?" Right? So, this just happens over and over. When I was younger, when I was first thinking about P versus NP, I, like, I had an intuition for what should be. And what I've understood over the years is that

• 37:03Speaker 00

  my intuition for what should be is often just wrong. And I'm, I'm having to revise my intuitions all the time. So, when something like this happens often enough, you start asking yourself, "What do I really understand?"

• 37:23Speaker 00

  Uh, do I really understand Pierszynski? Like, I mean, I understand the, the statement, right? Like, it's just one of those problems where somehow it is not so difficult to, to make formal, to write down mathematically, but to actually know what the answer is is just orders of magnitude more difficult than it is to phrase the problem. And complexity theory in particular is littered with statements like this where

• 37:58Speaker 00

  the, the space of algorithms is just that vast. So if you just, if you just keep getting surprised over time, you're just like, well, what, what do I understand? Maybe it was just misplaced confidence.

• 38:10Ryan Peterman?

  Okay, what about this one? So XP not equal to NXP? Or would you say next?

• 38:16Speaker 00

  Oh, NXP, yeah.

• 38:17Ryan Peterman?

  Okay.

• 38:18Speaker 00

  X versus NX. So this is like the exponential time of P versus NP.

• 38:24Ryan Peterman?

  For XP not equal to NXP or next, you gave it a 45% chance. And if this is the P not equal to NP equivalent, but for exponential time, why is your?

• 38:37Speaker 00

  Yeah.

• 38:38Ryan Peterman?

  Why is it so low?

• 38:39Speaker 00

  Oh, because exponential time algorithms are even more powerful. Did I really say 45%? I mean, for NX versus XP or NX versus co-NXP?

• 38:50Ryan Peterman?

  Yeah, NXP not equal to XP, 45%. It's in this table.

• 38:55Speaker 00

  So, so in other words, I believe NX equals XP more than I believe they're different. Right? So, um, yeah, let me try to explain why. So you can think of the NX versus XP question as some special case of P versus NP, where instead of looking at the arbitrary SAT problem, I'm looking at a SAT problem which is extremely compressible. So there's like a really small little computer.

• 39:32Speaker 00

  That is exponentially smaller than the length of the instance. And it just outputs the character on the line number and the column number for the Dymax CNF, like the CNF file. Okay, so it's like a extreme compression of like some file. So it's like you zipped it down to like something like exponentially smaller than its original length. Okay, so it's like some super compressed, extremely highly regular SAT instance. So I give you that and I ask you, when you unpack this thing, decompress it, is the result going to be satisfiable or not? And I want you to solve this

• 40:15Speaker 00

  in time polynomial in the decompressed representation. Okay, okay, so the point is that like this is SAT, but in some very special case where the thing is extremely structured. So the idea, um, one conjecture for why SAT solvers work um in practice, like one, I mean, this is, I mean, conjecture may be overkill because, I mean, this is just, this is not even a well-formed mathematical statement. So one hypothesis for why SAT solvers work in practice is because um, the real world is highly structured.

• 40:58Speaker 00

  The real world is governed by physical laws that are not random, they're not arbitrary. Like from a very small number of rules, we can recreate so much of science. So what arises in practice from designs of hardware and things like this are often extremely compressible. They have to be extremely compressible. And so maybe it's true that, you know, every which has a highly compact representation can just be solved efficiently. This is, this is the idea of whether, you know, NXP equals XP. That when it's really, really structured like that and super compressible,

• 41:43Speaker 00

  there is some advantage. It's not like a completely random. And since it's not like something arbitrary, it's no, it's in fact very, very special.

• 41:51Ryan Peterman?

  The other one is 80% likelihood on NXP equal to co-NXP. And you wrote, why would a self-respecting complexity theory do that? Yeah, I was curious why that's such a contentious statement.

• 42:08Speaker 00

  So NXP versus co-NXP. Let's, let's first talk about MP versus co-MP. So co-MP

• 42:17Speaker 00

  is like the class of sort of complements of MP complete problems, like, like unsat, like checking whether something's unsat. Now, from the time complexity point of view, there's no difference between checking sat and unsat. You can always flip the answer. But from the complexity point of view, if I, if I ask you, does co-MP equal MP? What I'm asking you is, could you prove to me that a formula is unsatisfiable with a short proof? When it's satisfiable, I can give you a short proof. I can just give you the satisfying assignment. You plug it in, check that it works. But if it's unsatisfiable, if there, no assignment works,

• 43:00Speaker 00

  we're saying for all assignments, the formula is not true. Can you flip that to an existential statement and say, oh, there exists this little proof. It makes it work. So people don't believe that MP is equal to co-MP. And in fact, like MP different from co-MP implies P different from MP.

• 43:22Speaker 00

  But so this is the exponential time version of MP versus co-MP. So it's co-NXP versus NXP. The reason why I think these are likely to be equal is that if a little birdie sat on an NXP machine's shoulder and gave it a little bit of advice about what the co-NXP thing is doing. Then the N X algorithm can actually solve co-N X problems. And so let me explain, uh, let me explain why. What's the little birdie, what the heck is the little birdie saying?

• 44:03Speaker 00

  So because N X problems can run in two to the N time and two to the N squared time and things like that. Running an exhaustive search over all possible inputs of length N is no problem for N X. So what a little birdie can do is say, okay, suppose, um, like I want to verify that this particular instance, like, let's say, we can talk about like an unset, but like, you know, some compressible unset problem or something. Suppose I want to prove that this compressible unset instance is a yes. Okay, how am I going to do that with N X?

• 44:48Speaker 00

  The little birdie will tell me the total number of inputs of length N, which are a yes. Okay, so it will, it will, it will just tell me some string which says, here's the total number of inputs of length N. You gave me a length N input, here's a total number of inputs of length N that are a yes. Okay, okay, so, um, this, this advice, this little, you know, birdie's advice doesn't take very much, like to encode account. It's like order in bits to encode account of things. So, um, so what does the N X thing do to prove a co-N X thing?

• 45:32Speaker 00

  What it does is it guesses the things which are a no. So I'm trying to prove unset, so unset means yes, sat means no. So the N X thing guesses those things which are no. The no things it can answer, right? If it's a sat thing, it can just guess the answer to each of the no's. Okay, so it guesses the answer to each of the no's. It verifies all those answers and then it checks the number of things it guessed is what the birdie told it. Once it's done that, all the no's have been covered. So everything else must be a yes.

• 46:12Speaker 00

  So that, so, so it can actually prove a yes by just exhaustively finding all the no's and ruling out any other no's.

• 46:21Ryan Peterman?

  But the big question in my mind is where do you get the little birdie?

• 46:24Speaker 00

  Where do you get the little birdie advice from? Yeah, yeah, so, yeah, so this, I've studied, yeah, this, um, what the little birdie gives you, and it seems to me that it is possible that this little birdie itself can be constructed in N X. And if so, then we'd just be done. Like in N X, you figure out what the little birdie would tell you and then use that to just flip the answer. Sort of guess, sort of guess all the things which are no's, so what remains must be a yes, and...

• 46:58Ryan Peterman?

  We talked a lot about time complexity, and you mentioned a little bit, this advice, I guess, is kind of space complexity. And I know you had a major result relating space and time complexity, basically simulating time complexity with space complexity, but lower than it's been done prior. Could you explain what it was before your breakthrough results? And then maybe the intuition behind your breakthrough result?

• 47:25Speaker 00

  In general, the problem is the following. I give you an algorithm that runs in time T, and I want to know, um, is there another algorithm that uses space much less than T? Uses the amount of memory, like, you know, units of memory much less than T? And still solves the problem completely, still completely simulates the thing perfectly.

• 47:53Speaker 00

  One intuition for why you might think, um, this question just can't be solved for some problems, there's just no way to improve on the space is if you think of like, the pro, like, a lot of problems in dynamic programming, like, let's say I have, um...

• 48:14Speaker 00

  Some logic circuit that I want to evaluate. And all the gates are provided to me in a row. And all the wires sort of flow from left to right. And then, you know, I start with information on the left. I want to compute the information on the far right. And all the, you know, all the bits are flowing left to right by wires. The natural way to evaluate such a circuit is you start with, say, the inputs on the left for each gate in turn in the line. You look at its inputs, its inputs have been determined, there's some bits. You use that to compute the value of that gate. You pass the values of that, of, you know, the output of that gate forward. Okay.

• 48:58Speaker 00

  But if that circuit, you know, has T gates in it, you know, it will take about T time to solve, but it will definitely also take about T space in general. Right? Like, the circuit could be wired up in some wild way and there just might not be a way to save space for an arbitrary circuit. But already in 1975, uh, people were studying this kind of, of question and finding counterintuitive answers to it. So, um, Hopcroft, Paul and Valiant, uh, based on work of Patterson and Valiant, uh, showed

• 49:39Speaker 00

  that time T arrhythms, at least in this so-called multi-tape Turing machine, uh, model, very powerful model, uh, can be simulated in space T divided by a log of T. So, I mean, it's like, uh, like you, you get some space savings, but it's only like a, a log T factor. Okay. Um, and the way this is done is, is quite, uh, counterintuitive. Uh, it was, I mean, uh, even though there's only a log factor there was, uh, pretty shocking. That development was.

• 50:18Speaker 00

  Extended to random access models of computation later. And and in more general models of computation, so like in in the late 70s and early 80s. So so it was known for pretty much any reasonable model of computation that time t can be simulated in space about t over log t. But there was a hidden, maybe not so hidden, gotcha in the space efficient simulation. It needs an exponential amount of time to run. So like you, there's a time-space trade off. Okay, if you really want to save some space, you got to blow up the time by a lot.

• 51:02Speaker 00

  Nevertheless, yeah, it was kind of commonly conjectured that this t over log t space was about the best you could do and you and that you were probably not going to get t to the 0.9 space or, you know, something, something much more efficient. So, yeah, it was a big surprise to me like that you can actually put time t and space about square root of t. Again, there's an exponential running time, just to, you know, give the full caveat out

• 51:42Speaker 00

  there, but but it's still very surprising, like this holds for any kind of time t algorithm, like including something that might be outputting, you know, something pseudorandom, some, you know, something from cryptography, you know, like it's not at all obvious that every such process could be compressed to only be need like square root of t space and still get the job done, still compute whatever function was being computed.

• 52:14Ryan Peterman?

  I mean, I know it's probably super involved, but if you could just, high level, what's the trick? How'd you do it?

• 52:19Speaker 00

  Well, the trick for me was to read James Cook and Ian Mertz's paper on tree evaluation very, very carefully, though. I mean, and just knowing the landscape around P versus P space and knowing what Hopcraft, Paul and Geyen did.

• 52:41Speaker 00

  Yeah, so but I I can give you a very high level idea of kind of what's going on and how what they did is useful. So Hopcraft, Paul and Valiant, the way they were modeling space bound and computation was in a particular way that seemed pretty general at the time, but turned out to be restrictive

• 53:08Speaker 00

  in ways that we just didn't anticipate. So the way they thought of it was, um, I'm gonna take like certain, I'm gonna break the computation up into little pieces. And I'm gonna like write, I'm gonna write pieces of the computation, like little bits into the memory, but I'm only gonna do that over blank space. I mean, this is something that sounds natural, right? Like, so like, I'm gonna erase pieces of memory and then I'm gonna overwrite that blank space with a piece of memory. So I'm being very destructive in a certain sense. Like, but this is a natural thing you do, right? Like, if you want to replace, you know, swap something with something else,

• 53:53Speaker 00

  you often just erase. But there are ways to swap without erasing, right? So there's like a common little trick that is taught in CS courses. So like if you if you require everything to be written into a blank register, then if you want to swap the contents of two variables like X and Y, then you've, you've got to have a temporary register. Like you move one into the temp, you erase it, you move Y into, into there and then so on, right? But if you don't want a temp, you can achieve the same thing

• 54:35Speaker 00

  with just exhoring the, the registers bitwise. Or if you've got numbers, you can add and subtract. Okay? In three instructions, clever instructions, adding, subtracting, or exhoring, you can actually swap the contents of two registers without needing a third. Okay, this is kind of the starting point for thinking about like, well, why does it matter? If you're always writing into erased memory? So, so what James Cook and Ian Mertz showed at a very high level was they, they were studying a certain problem called tree evaluation, whatever that is.

• 55:18Speaker 00

  And they were, the problem had an algorithm where you're all, you had a little stack and you're always sort of like, um, you know, popping and, and pushing on the stack, but you were always, you know, writing, uh, writing computation contents into erased memory. Okay. What they realized was that if you allow computations to exhore bits of memory into existing memory, then you can save a lot of space. So if you're really, really careful about how you exhore things, you can basically recover,

• 56:01Speaker 00

  uh, like what's in your memory without storing all of it at once. You sort of offload things to computation and you exhore on top of things very, very cleverly. You can get like nice cancellations of things you don't want and, and keep around things you do want. Yeah. So, I mean, that is a high level idea of how this stuff works.

• 56:24Ryan Peterman?

  And then going to square root, is it just an extension of that or is it a completely different?

• 56:29Speaker 00

  So the, the way it works with square root, a square root just happens to be kind of like the optimal trade off in this tree evaluation business. So, so what you do is you break the computation into square root of T time intervals and each time interval has about square root of T, um, steps in it. And what you do is you you give a particular way of simulating this thing. So that you're only kind of holding about a constant number of blocks. Or like of these time intervals in memory at any point in time. Like you're only holding a small number of these time intervals.

• 57:14Speaker 00

  Like or records of time intervals in memory any any point in time. Just entirely not obvious how you would do it. But but it's some sort of like it's some sort of sweet spot to set the square root of T. It's a way to it's like the the minimum setting of like trade off. Like say I have like, I want to break the computation in the intervals. And the intervals have a certain number of steps. If I if I set it to be square root of T, then the number of intervals and the number of steps in each interval is about the same.

• 57:44Ryan Peterman?

  So, I mean, that was a long held result. I mean, you you mentioned it was 1975. That's maybe

• 57:50Speaker 00

  Yeah.

• 57:51Ryan Peterman?

  Almost 50 years where

• 57:52Speaker 00

  Yeah.

• 57:52Ryan Peterman?

  If you come up with something like that and you you I guess you're writing it out, you're thinking through. And then you see it. What is that moment like?

• 58:00Speaker 00

  So I you know, I'm I've been around long enough to have been deceived by myself many, many, many, many times. So, yeah, I guess the the first two or three times I thought about this.

• 58:17Speaker 00

  I just thought this is another one of those ideas that can't possibly work. There's no way. There's just no way this works.

• 58:26Speaker 00

  So I would just kind of leave it. And then come back to it sometimes when I was bored of whatever else I was working on. Like I I it was a pretty slow process of convincing myself that this could possibly be true. Like I I thought there was.

• 58:45Speaker 00

  Either a bug in what James and Ian was doing somewhere, or there was a bug in my interpretation of what's happening. Um, I thought there had to be a mistake for a long time. And the only way I got over that was just writing it down, uh, over and over and over in different ways. Sort of writing and rewriting and writing and rewriting and adding more detail. And then maybe finding a different way of explaining it and erasing and, you know, writing something shorter and just sort of re-explaining it to myself over and over and over.

• 59:27Speaker 00

  And even then, like when I submitted it to the, um, stock conference where it was, where it appeared, um, I wasn't entirely confident that it was correct. I was just exhausted from like thinking about it for so long and just thought like, maybe someone else will find the mistake for me. Like I'm, like I, like I, at this point, like I, I was just like desperate. Like I had actually sent it to two colleagues that I trust, you know, privately and asked them, can you help me find the mistake? Or whatever, can you help me understand this? And one of them just said, like, they're, basically they just didn't read past the abstract.

• 1:00:08Speaker 00

  They're like, I'm not, I'm sorry, I'm not going to. I'm like, they just didn't believe it, period. Just like me, I mean, they didn't believe it. And, uh, another one said after a long time, well, I didn't quite, um, follow it, but there was a footnote that you put like in, in the bottom of some page. After that, after that footnote, then I began to believe it. So then what I did was I just took that footnote and elaborated it in, in like a later revision, sort of made it the, what I called the warm-up. Because I was like, yeah, I, I've got to do, I've got to write this thing in a way.

• 1:00:52Speaker 00

  That is airtight so that other people will actually believe this. Because, yeah, it took me a long time to get used to it, to believe it, yeah.

• 1:01:02Ryan Peterman?

  Wow. What motivates you to solve these hard problems? I mean, what keeps you driven? Because you kind of, it sounds like you gotta just bash your head against the wall. And maybe you get there, maybe you don't.

• 1:01:20Speaker 00

  I try not to bash my head against the wall. And if I'm going to do it, it's gonna be, you know, a comfortable wall. It's gonna be, you know, one that's like, high-end and luxurious or something. Like, I'm gonna enjoy the process, is what I mean. Like, if I don't enjoy the process of really grinding and trying to understand something, I'm not gonna do it. Like, so I think that, if, you know, if anything is one thing that I like.

• 1:01:59Speaker 00

  I like to involve myself in working on problems where the grind is actually joyous and fun. Yeah. For the other things, they're mainly opportunistic. They're mainly me just taking something that new that I see and just fully integrating it with everything I know and following everything to the logical conclusion. And just seeing what happens. Like, trying not to get emotional, trying not to whatever. Just trying to follow everything, one step after another, yeah.

• 1:02:35Ryan Peterman?

  How do you pick good research direction?

• 1:02:38Speaker 00

  The best kind of research direction, which is very hard to, it's very hard to come across, is a direction where you've set yourself up in a way that you can't lose. That like, I have a hypothesis, H, and one of two things is going to happen. Like, either I prove H is true, or I refute H, prove not H. What I would like to have is a situation where if H is true, then good things happen. If not H is true... Good things still happen, other, other good things. Like, um, like I like to look at things where, yeah, it's a win-win.

• 1:03:24Speaker 00

  Kind of, if, if you can find opportunities like this, this is important. Like, I think often I'm not looking at a specific, uh, problem. I'm looking at a method. I'm looking at the technique. You know, I'm looking at not the specific proof, but like, like the space of ideas. And I'm trying to understand what else can be done in the space of ideas. Like, so, so often I solve problems just like, by just taking some idea and putting it somewhere, somewhere else.

• 1:03:59Ryan Peterman?

  Do you have a concrete example of where you've, you've pursued something, knowing that if you succeed, good. If you succeed in the other direction, also good.

• 1:04:09Speaker 00

  I have some particular research program for, which if it materializes, would actually show that something called the orthogonal vectors problem can be solved in nearly linear time. Okay. Now, this, um, now if that's true, then the SAT problem can be solved in about the same time as subset sum. It could be solved in like square root of two to the n. So this would like truly break, uh, strong ETH in like a radical way. Okay. And, um, I did a lot of work, uh, in the past, showing how if, uh, you can improve

• 1:04:54Speaker 00

  on the running time of SAT, then you can somehow use that to prove circuit complexity lower bounds. You can take an algorithm for analyzing circuits. That's non-trivial and interesting and turn that into a limitation on what those circuits can compute. Okay. So, so this hypothesis, maybe, maybe I won't exactly say what it is. It's, it's a pretty technical statement, but the point is that if the hypothesis is true, then I get this fantastic algorithm for this orthogonal vectors problem. I get this algorithm for SAT. I get circuit complexity lower bounds from that.

• 1:05:38Speaker 00

  I get to somehow prove limitations on what circuits can do.

• 1:05:43Speaker 00

  If the hypothesis is false, I can use that hypothesis to actually show another circuit complexity lower bound of a different flavor. So regardless of whether or not like the hypothesis is true or false, like I'm going to make progress in complexity theory. I'm going to prove a new limitation one way or the other. Right? So it, so sometimes like, I mean, this can be difficult to do, but um, usually what has happened instead of something so clean is that I have, I, I read about some idea or whatever. I try to apply the idea. I read about some magical algorithm.

• 1:06:25Speaker 00

  I try to apply the magical algorithm to solve something like SAT. It doesn't work, but I look at my approach. I stare really hard at it. I try to pivot, you know, I try to just extract what I can. And then I get some other type of algorithm. I mean, this is essentially how I proved um, like the circuit complexity lower bounds that, that first got me a job at Stanford was I was trying to solve SAT faster with some algorithm. It didn't work, but then I realized that that algorithm worked for a large class of circuits, including ones we didn't know lower bounds for. So then I use that to prove a lower, a lower bounds. Yeah.

• 1:07:07Speaker 00

  So, I mean, um, this is just a general principle that, that I've had.

• 1:07:13Ryan Peterman?

  What, what would be your book recommendation if someone wants to learn more on complexity theory?

• 1:07:19Speaker 00

  Yeah, so it sort of depends on how deep uh, you want to go. There's Avi's book. Yeah, Avi's book is really nice. If you're looking for something a little more gentle of an introduction, um, I would say like you could read the early chapters of Lance Fortinell's uh, The Golden Ticket. Like trying to imagine what a world would be like if P equaled NP. Um, I, it, I, I like that imagination exercise that, that Lance uh, did.

• 1:07:52Speaker 00

  On a more technical level, you know, if you're looking for something slightly more technical, you could look at the nature of computation by Mertens and Moore, I think. So this is, this is still not, you know, very technical, but, but a lot, but it is a textbook, right? Yeah. And then, of course, Sipsers' introduction to the theory of computation is like a fairly concise and very well-written textbook. Yeah.

• 1:08:31Ryan Peterman?

  Last question for you is if you could go back to the beginning of your career, knowing what you know now, what advice would you give yourself?

• 1:08:38Speaker 00

  So I guess like one thing that I did by accident, I guess, which I think people should keep in mind is that you don't need permission to work on very tough problems. Like, and in fact, the tougher the problem, like in complexity theory, there are all these problems where, like, really, nobody has a very good clue of what to do beyond like a few simple structural results, like, so that kind of levels the playing field a bit. And, yeah, like, you just, you don't need permission to think about these problems. You don't need like, you know, anybody's say-so or whatever.

• 1:09:23Speaker 00

  I mean, that's, that's one thing that I would like younger people to keep in mind, that, I mean, this knowledge is open to the world and it's open to you and, and you can just go learn it and think about it and you don't, yeah, you don't need any, anybody's permission, especially not mine. Yeah, like, another thing I think is to avoid inertia, in the sense that like, you know, if you, if you don't think about and reflect, like, where am I going and what am I doing? You can, you know, you can just end up coasting in a certain direction.

• 1:10:09Speaker 00

  And I think it's important for people to sit down and truly reflect and think from time to time, like, okay, if I keep going in this direction, is this going to lead to a place that I want to be? And this sort of advice is good for all aspects of life, really. Like, like, if I keep, if I keep, you know, just allowing things to be the way they are, am I going to be okay with that? Or do I need to do something? Do I need to, so it's like a little interrupts, you know, in your life, reflection and just sort of like, okay, is this, is this where I, do I, do I need to be coasting here?

• 1:10:52Speaker 00

  Like, do I need to, yeah, I think, um, like in research for me, I was always reevaluating, like, okay, you know, what did I do last year? And what did I do the year before? And, you know, could, you know, like, what do I know now that I didn't know then? And like, you know, am I progressing? I think like, like that sort of self-evaluation is crucial when you're in grad school because, you know, once you're in a PhD program, there are no more like easy metrics to gauge like how good or bad you are doing. And the truth is, you're just doing like, you know, like, like there, there just isn't such a metric.

• 1:11:35Speaker 00

  So all you can really do is evaluate your past self with your present self and compare and contrast to, to see if you're making progress with whatever it is you want to do.

• 1:11:49Ryan Peterman?

  Thank you so much for your time, Professor Williams. I really appreciate it.

• 1:11:52Speaker 00

  Yeah, I appreciate you having me here. It's been fun. Thanks.

• 1:11:56Ryan Peterman?

  Hey, thank you for watching this podcast. If you liked it and you want to see the show grow, please support with a comment or a like. Also, if you have any recommendations for people you want me to bring on, please drop a comment. Guests like Barbara Liskoff, Mike Stonebreaker, Mark Booker, these were all people that I brought on because someone left a comment. On another note, aside from the podcast, I'm working on building the ergonomic keyboard that I wish existed. Here's a glance at the prototype. It's a split keyboard, so there's two sides. This is in the case. But yeah, we launched on Kickstarter and we hit our goal within eight hours of launching. I really appreciate it if you were one of the people who grabbed one of the early units. We're now working on the long journey of building the tooling now. And so if you still want to pick one up,

• 1:12:41Ryan Peterman?

  I've left the late pledges open on Kickstarter, so you can grab one there. I'll put a link in the description. Thank you again for watching the podcast and I'll see you in the next episode.