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

Episode Date: June 29, 2026

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).• 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-donePodcast 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-leetcodeThank 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) OutroWhere 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/rrwilliamsWhere 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/@ryanlpetermanReferenced 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

Hypotheses which are at the edge of our understanding can be enlightening. This is Ryan Williams. He's a professor at MIT who won the Girdle Prize for theoretical computer science, and I started by asking him a leak code question. So the question is threesome. Can you do better than n squared for this? Yeah, you actually can do better than n squared. And this is not at all obvious.

He also had contrarian takes on popular hypotheses. 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. Okay, I want to start by asking you the most popular leak 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. Yes. And so what are your thoughts on the brute force solution for this? We can start there. 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 three sum 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, um, whose sum with A is going to be zero. Okay. So the way this works is after you sort the numbers, you, 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 the men 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 men and the

max is either 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. 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 just can't be a solution. And so the number of times you move, you know, your fingers in total is like N.

So you have an order in solution for finding that extra pair. And you do this for each of the number is A. Okay. So then you get an order in squared solution overall. You do it n times. Each finger search takes order in time. And that is the popular solution. the popular solution.

A lot of people know when we're in these algorithmic leak code interviews. And I know a lot of your research is kind of about pushing lower bounds. So maybe we can start that conversation off by can you do better than N squared for this? 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 day. 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 in size or square root log in. It's like a really small little group, okay? So you've got either n over log in groups total or n over square root log in groups total depending on how you break up your groups.

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's 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 three-sum 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 pre-processing that you do 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 searched through like a group of length G and another group of length G would take about order G time. And you can actually do faster by this kind of lookup, this kind of table look up. I think it is kind of like you take this list of length in and you kind of shrink it into like N0. end over group size number of things.

And these are more complicated objects. And then you do, and now like you're trying to speed up like the check over these like small complicated objects for like, should I move my finger to the right? No, is there nothing in this group? Would finger search just go straight through this group or not? This is basically what you're asking. So the unit that you're operating on is not a single integer. it's a group.

Yeah, it's like a group of them. So you use some kind of table lookup. And so, well, it's much fancier than a table lookup, actually. It goes through some other model called the linear decision tree model. So it's like in some weird model where you can actually get a faster three-sum solution. You can get an end of the 1.5 solution. It's a really interesting and sophisticated solution. But what I want to emphasize is it starts from the finger search solution.

and sort of like figuring out how to like process finger moves faster. So do pre-processing so that finger moves can go faster. Yeah, I saw the time complexity of this. It's n squared, divided by log n, divided by log-n, all raised to the two-thirds. Is there any intuition behind? I mean, that's just crazy. 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 different kind of lookup table a different kind of set of tricks and you know maybe there is some savings you can do here and there by sort of compressing things a little differently so that yeah there are several albums

that beat the N squared running time bound and they all to my knowledge kind of work in a similar type of way like they're they're taking this in squared time, algorithm and finding little ways to like pre-process and then optimize based on the pre-processing, like make

finger searches faster and things like that. It's sort of, yeah. A lot of your research is on this topic of fine green complexity or kind of lowering lower bounds. So maybe you can explain what is fine. Lowering lower bounds. I like that.

Yeah, lower. The idea behind fine grain 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 complication? So what if we just focus solely on the time complexity of a problem, like the fastest algorithm

that will solve that problem? 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 into the 10, into the billion, whatever. And so like showing that something's not in P 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 end of the 3 minus epsilon for some epsilon? 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. 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 by just a little bit. This actually leads to a different notion of complexity. You can even take an MP-complete problem and a P-problem and reduce the MP 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 in 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 in numbers, there's two to the end possible subsets. The obvious algorithm takes to the end

time. Okay. 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. So you can get a algorithm which runs in square root of to the end 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 meat-in-the-middle type 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

in over two in over two you enumerate all the subset sums on the two halves so you have two to the to the end over two possible sums for like the first half two to the in over two possible sums for the second half then you want to know is there a number from the first half you know 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 the two-sum problem, which you can solve by sorting in binary search. And this is a reduction. We have shown how to solve a subset sum problem, like which would normally take to the end time in square root of two-the-end time. The MP complete problem by reducing it to a problem like two sum, the obvious algorithm there takes in squared time, trying all the pairs of numbers to see if they sum it to a target and using an n-log-in time algorithm for that.

So fine-grained complexity can relate problems that would not be relatable at all in the traditional P versus MP theory. Like one problem is incomplete, the other problem is not. so they should not have a polynomial time reduction between them, like in general, right? But if you just look at the time complexity and you focus on, okay, I have an algorithm, two to the n-hour rhythm, is it the best possible? Then I have an n-squared algorithm,

is it the best possible? Then you can relate the two problems. And this is a general phenomenon that you can relate problems that look like they should have nothing to do with each other. So you talked about, You talked about reducing subset sum to two sum, but subset sum is an arbitrary integers that sum to the target sum, right? Yeah, so the idea is nobody said I had to use a polynomial time reduction or something like that to reduce one problem to another.

So what happened? What happened the trick was I took this subset sum problem that had in 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 two-the-end numbers. Now, I can solve two-sum in linear time, so solving that instance gives me a square root of two-thian time algorithm for the original problem. But yeah, in the meantime, going from one problem 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. I get it. Okay, so the reduction, it's kind of like the, if you solve the subset sum, you have some time complexity. And if you translate it to the other problem, you lose a little bit of time complexity,

but less than the aggregate. 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 two sum, then I can improve the obvious algorithm for subset sum. And that's what this thing achieves.

Because I know how to get a faster album for two sum. I can get one for subset sum. So you just want 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. In one of your talks, you mentioned preserving magic between. Right. Okay, so this is that.

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, 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-in, time out of them. 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. There is a clear shortcut 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. some, get an algorithm for a subset sum, but avoids trying all of the to the end subsets. So I understand one of the driving motives for pursuing this, I guess, lowering of lower bounds, is that strong exponential time hypothesis, or I see it SETH. Could you explain that and its significance? Strong E.T.H is like a severe strengthening of the P.V.

versus MP question. So P versus Zimpe is asking whether the SAT problem 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.999 to the end time algorithm. To say the hypothesis totally precisely, it has to do with the K-Sat problem, and you're looking at clauses of length K or arbitrary K, but those details don't matter so much. It's a canonical MP-complete problem. Sat is solved all the time in practice. It's extremely useful for verification nowadays. 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. So the hypothesis that it needs, say, 1.999-99-99-9-9-9 to the end time for all strings of nines is a very strong, exponential time hypothesis. It's what's stronger than P-Den from MP. It says, no, no, no, no, it's not super polynomial. It's actually darn near to the end time that you need. Right. And so do you think that hypothesis is true and, you know, why or why not? I think I'm on the record as not believing this hypothesis. Yeah. Yeah.

Why don't I believe this hypothesis? 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 starting TH, I guess that shows how old I am. I was trying to think about how to solve this so-called C-Sah. DNF SAT problem faster than to the end. And, well, at the time, there were a number of other MP complete problems that had

faster algorithms, like subset sum. So I thought, well, there's not, I mean, what's so special about SAT? 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 end 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 album for that but this is a more general version of set um 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. They 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?

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 a, like, a variety of other problems instead. And so after a while, I realized that the truth value of strong ATH 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.

And so by trying to think about, okay, what would an algorithm that breaks to the, in look like? What could it look like? I sort of force myself to think in a different way. I have to like discard other natural algorithmic possibilities because we know they won't work. And I have to think 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. I mean, 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, well, I mean, I believe this is a minority opinion, right? Why would they go against?

I mean, I think, for example, Russell and Palliazzo, a good friend of mine who helped propose this, I mean, he always emphasizes to me, well, this is this is. a hypothesis. It, you know, we didn't, 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.D.M. for MP 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 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 H 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. If you can improve on the albums 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. 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.

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 Dimex C and F 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 and negations, they're often called literals. Okay, so I take an or of these literals. 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 DIMAC's file. And so it's an and of a bunch of ores, and each oar has some small number of literals in it. Call it K. So usually the width is called K. And so the K-SAT 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.

So that's the most popular version. That's what SAT solvers, you know, turn 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 ores 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 in this representation with a bunch of variables,

is there a way to set the variables to make this true? That's formula sat. You could also look at circuits of bounded depth, as you mentioned. So there is this 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 ores and ants. So these circuits are made up of ores and ands, like in layers. So the CNF representation is a special case where I have an and of oars,

like an and of a bunch of clauses and oars 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. And because the idea is you only have some constant number of layers of these and doors. And you can look at the SAT problem on circuits like that as well, for example. Those are two other versions that people look at. 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 exist solutions that are

asymptotically better than 2 to the N. So I guess it, it, it, in the, the larger K can be the more difficult. Yes, that's the intuition. That, that is the intuition. Okay, have you ever plotted that curve? Like, is it, does it drop off, you know, exponentially or? Yeah, yeah. Yeah, that's what's so interesting, uh, about the current state of the art in K-sat algorithms.

as K increases, all of them, all of the different types of algorithms you might try to run, they all approach a two to the end exponent. Like as K grows and grows and grows, they get 1.99, 1.999, 1.999 and so on. And yeah, it drops, I mean, in other words, it goes towards two pretty quickly, actually. So we understand how the exponent behaves pretty well for the known algorithms we have. And then for something like 3Sat, what is the intuition behind speeding up an exponential time search? Yeah. So for 3Sat, let's just look at a single clause, okay?

A clause that's got three variables in it. Okay? we know that 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, two 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 one easy way to see that two set can be solved in less than two the end time 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 in assignments, and we would like plug in, you know, So 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's a difference. So we reduced by three variables at the cost of seven recursive calls as opposed to eight. And this gets you a slight improvement. This gets you about 1.9-2 to the end. Something slightly better than two to the end. Okay, but you can do better than this. But 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. When I was thinking about circuits and the different ways, and depths. I don't know if this is an unusual question, but it reminds me of neural nets, but the operators are different, and the space of the literals is different. So instead of bullions, 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 analogs in between these two spaces? Yes, yes. So yeah if we look at say i want to model a neural network on so i want to compute say it's still a bullion function but i want to do it with like a neural network so like i want to use let's say

ray lus or um sign activation functions or what have you um there is a slightly more general like gate that we can use instead of oars and ands. That turns out to basically be equivalent. So if instead of using ores and ans, we use a so-called majority gate, 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 function. So if they have a constant number of layers of neurons, we can get a constant number of layers of majority gates 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. Still using Boolean's. We're still looking at Boolean inputs, though. Yes. So once you allow your input space to be larger and have floating points,

then you can prove a lot more in terms of lower bounds. You can find things that take, like, depth three in the neural net that can't be done in depth two and so on. 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. Open AI, Anthropic, Cursor, and Versal 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 ARBAC, 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 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 pulled a few of these that were kind of minority opinions or maybe less common takes. So here's to hear your rationale. Okay, okay. One of them, the well-known one, you know, P not equal to MP or P versus MP,

you assigned an 80% confidence that they're not the same. Yes. And I think most people say, much higher confidence. So why do you, why would you assign such a low confidence that they're not the same? 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, no, I know, he was, he sort of called me out and 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, 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 expect to be true. But all the time in algorithms, people are finding algorithms where it's just like surprising.

Just wait, what? 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 MP, I, like I had an intuition for what should be. And what I've understood over the years is that my intuition for what should be is often just wrong.

And 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? Do I really understand beer city? I mean, I understand the statement, right? Like, it's just one of those problems where somehow it is not so difficult

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. Complexity theory in particular is littered with statements like this where the space of algorithms is just that vast. So if you just keep getting surprised over time, you're just like, well, what do I understand? Maybe it was just misplaced confidence. Okay.

What about this one? So Xp not equal to NX or would you say NXP? Oh, NXP. Yeah. X versus NX. So this is like the exponential time of P versus NP. For X not equal to NXP or NXP, you gave it a 45% chance. And if this is the P not equal to NP equivalent, but for exponential time, why is it so low?

Oh, because exponential time albums are even more powerful. Did I really say 45%? I mean, for NX versus X or NX versus K. co-Inxp. Yeah, N-Xp not equal to X 45%. It's in this table. So in other words, I believe NX equals X more than I believe they're different. Right. So, yeah, let me try to explain why. So you can think of the NX versus X question as some special case of P versus MP, 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 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 Dimax CNF, like the CNF file. Okay. So it's like an 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 compress, extremely highly regular sat instance. So I give you that and I ask you, uh, when you unpack this thing, decompress it is the result going to be satisfiable or not. And I want you to solve this in, time polynomial in the decompressed representation. 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, one conjecture for why SAT solvers work 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 the real world is highly structured. 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 sense, which has a highly compact representation, can just be solved efficiently. This is the idea of whether, you know, in X equals X. That when it's really, really structured like that and super compressible, there is some advantage.

It's not like a completely random. And since it's not like something arbitrary, no, it's in fact very, very special. 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.

So NX versus co-NX. Let's first talk about MP versus co-MP. So co-MP is like the class of sort of compliments of MP complete problems, 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. From the complexity point of view,

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's no assignment works, we're saying for all assignments, the formula is not true.

Can you flip that to an existential statement and say, oh, there exists a little proof that makes it work? So people don't believe that impasseh. is equal to co-MP. And in fact, like, MP different from co-MP implies P different from MP. But so this is the exponential time version

of MP versus co-MP. So it's co-NX versus NX. The reason why I think these are likely to be equal is that if a little birdie sat on an N-X X-Nex machine's shoulder and gave it a little bit of advice about what the co-inex thing is doing,

then the NX algorithm can actually solve co-inex problems. And so let me explain, let me explain what the little birdie, what the heck is the little birdie saying. So because NX problems can run in two to the end time and two to the end squared time and things like that. Running an exhaustive search over all possible inputs of LinkedIn is no problem for NX. So what a little birdie can do is say, okay, suppose, like I want to verify that this particular instance, let's say, we can talk about like an unsat, but like, you know, some compressible unsat problem or something. Suppose I want to prove that this

compressible, unsat instance is a yes. Okay. How am I going to do that with NX? The little birdie will tell me the total number of inputs of length in, which are a yes. Okay. So it will just tell me some string, which says, here's the total number of inputs of lengthen. You gave me a lengthen input? Here's a total number of inputs of lengthen that are a yes.

Okay. Okay. So this, this advice, this little, you know, Bertie's advice doesn't take very much, like to encode account. It's like order in bits to encode account of things. So, so what does the annex thing do to prove a co-enex thing? What it does is it guesses the things which are a no. So I'm trying to prove unsets. So unsat means yes, sat means no. So the annex 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 noes. Okay. So it guesses the answer to each of the nose. It verifies all those answers.

And then it checks the number of things it guess is what the birdie told it. Once it's done that, all the nose have been covered. So everything else must be a yes. So it can actually prove a yes by just exhaustively finding all the nose and ruling out any other nose. But the big question in my mind is where do you get the little birdie? Where do you get the little birdie advice from? Yeah, yeah. So yeah, so this, I've studied, yeah, this, what the little birdie gives you.

And it seems to me that it is possible that this little little. birdie itself can be constructed in NX. And if so, then we'd just be done. Like in X, you figure out what the little birdie would tell you, and then use that to just flip the answer. So guess, let's sort of guess all the things which are no, so what remains must be a yes. And we talked a lot about time complexity. And you mentioned a little bit, this advice is kind of space complexity.

And I know you had a major result relating space and time. complexity. They're 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? In general, the problem is the following. I give you an algorithm that runs in time T. And I want to know, 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 solve the problem completely still completely simulates the thing perfectly one intuition for why you might think um this question just can't be solved or some

problems there's just no way to improve on the spaces if you think of like the pro like a lot problems in dynamic programming. Let's say I have 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, 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, if 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? 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, people were studying this kind of question

and finding counterintuitive answers to it. So Hopcroft Paul Invaliant, based on work of Patterson, and Valiant showed that time T-R-R-R-Thom, at least in this so-called multi-tape Turing machine model, very powerful model, can be simulated in space T divided by log of T. So, I mean, it's like a, like you get some space savings, but it's only like a log T factor. Okay. And the way this is done is quite counterintuitive.

It was, I mean, even though there's only a log factor there was pretty shocking. That development was extended to random access models of computation later and more general models of computation. So like in the late 70s and early 80s. 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 tradeoff. Okay, if you really want to say, some space, you got to blow up the time by a lot. Nevertheless, it was kind of commonly conjectured that this T over log T space was about the best you could do, and 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 there.

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 pseudo-random, 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. I mean, I know it's probably super involved, but if you just, you know, high level, what's the trick? How'd you do it? Well, the trick for me was to read James Cook and Ian Mertz's paper on tree evaluation very, very carefully. I mean, and just knowing the landscape around P versus P space and knowing what Hopcroft, Paul, and Giant did. Yeah, so I can give you a very high-level idea of kind of what's going on and how. what they did is useful.

So Hopcroft, Paul, and Vion, the way they were modeling spacebound and computation was in a particular way that seemed pretty general at the time, but it turned out to be restrictive in ways that we just didn't anticipate. So the way they thought of it was, I'm going to take, like, certain, I'm going to break the computation up in little pieces. and I'm going to like write I'm going to write pieces of the computation

like little bits into the memory but I'm only going to do that over blank space I mean this is something that sounds natural right like so like I'm going to erase pieces of memory and then I'm going to 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, 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 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 got to have a temporary register. Like you move one into the temp, you erase it, you move Y into there, and then so on, right? But if you don't want a temp, you can achieve the same thing with just exoring the registers bitwise. Or if you've got numbers, you can add and subtract.

Okay. In three instructions, clever instructions, adding, subtracting or exoring, you can 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 riding into erased memory? So, so what, uh, James Cook and Ian Merritt showed, uh, at a very high level was they, they were studying a certain problem called tree evaluation, whatever that is.

And the problem had an algorithm where you're all, you had a little stack and you're always sort of like, you know, popping and and pushing on the stack. But you were always, you know, writing computation contents into erase memory. Okay. what they realized was that if you allow computations to exor bits of memory into existing memory, then you can save a lot of space. So if you're really, really careful about how you exor things, you can basically recover like what's in your memory without storing all of it at once. You sort of offload things to computation and you XOR on top of things very, very cleverly.

you can get like nice cancellations of things you don't want and keep around things you do want. Yeah. So, I mean, that is a high level idea of how this stuff works. And then going to square root, is it just an extension of that or is it completely different? So the way it works with square root, the square root just happens to be kind of like the optimal tradeoff 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 steps in it and what you do is 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, like records of time intervals in memory, any point in time, which is entirely not obvious how you would do it. 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 minimum setting of like tradeoff.

Let's 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. So, I mean, that was a long-held result. I mean, you mentioned it was 1975. That's maybe almost 50 years where if you come up with something like that, and I guess you're writing it out, you're thinking through, and then you see it.

What is that moment like? So, you know, I've been around long enough to have been deceived by myself many, many, many, many times. So, yeah, I, yeah. I guess the first two or three times I thought about this. 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.

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, it was a pretty slow process of convincing myself that this could possibly be true. Like, I thought there was either a bug in what James and Ian was doing somewhere, or there was a bug in my interpretation of what's happening. 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 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 writing something shorter and just sort of re-explaning it to myself over and over and over.

and even then, like when I submitted it to the stock conference where it was where it appeared, I wasn't entirely confident that it was correct. I was just exhausted from like thinking about it for so long and just thought maybe someone else will find the mistake for me. Like I'm like at this point like I was just like desperate. Like I had actually sent it to two colleagues that I trust, you know, private. 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, basically they just didn't read past the abstract. 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 another one said after a long time, well, I didn't quite. follow it, but there was a footnote that you put, like, 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 like a later revision and sort of made it what I called the warm up because I was like, yeah, I've got to do, I've got to write this thing in a way that is erotite so that other people will actually believe believe this because yeah it took me a long time to get used to it to believe it yeah wow what what motivates you to solve these hard problems i mean what keeps you driven because you kind of sounds like you got to just bash your head against the wall and maybe you get there maybe you don't i try not to bash my head against the wall And if I'm going to do it, it's going to be, you know, a comfortable wall.

It's going to be, you know, when it's like high end and luxurious or something. Like, I'm going to 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 just, I'm not going to do it. Like, so I think that if, you. You know, if anything is one thing that I like. I like to involve myself and working on problems where the grind is actually joyous and fun. Yeah.

For the other things, they're just, they're mainly opportunistic. They're mainly me just taking something that knew that I see and just fully integrating it with everything I know and following everything to the logical conclusion. and just seeing what happens. Trying not to get emotional, trying not to whatever, just trying to follow everything one step after another. Yeah. How do you pick good research direction? 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 I like to look at things where, yeah, it's a win-win. Kind of, if you can find opportunities like this, this is important. Like, I think often I'm not looking at a specific 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. done it in the space of ideas. So often I solve problems just by just taking some idea and putting it somewhere else. Do you have a concrete example of where you've pursued something knowing that if you succeed, good?

If you succeed in that direction, also good. 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, 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 the end. So this would like truly break strong ETH in like a radical way. Okay. And I did a lot of work in the past showing how if you can improve 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 I won't exactly say what it is. 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 balance from that. I get to somehow prove limitations on what circuits can do. 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 the hypothesis is true or false, 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 usually what has happened instead of something so clean is that I have, I read about some idea or whatever.

I try to apply the idea. I read about some magical algorithm. I try to apply the magical algorithm to solve something like SAT. It doesn't work. But I look at my approach. I stay really hard at it. I try to pivot. 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, like, the circuit complexity lower bounds 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 bounce. Yeah. So, I mean, this is just a job. general principle that that I've had.

What would be your book recommendation if someone wants to learn more on complexity theory? Yeah, so it sort of depends on how deep 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,

I would say like you could read the early chapters of Lance Fortnell's The Golden Ticket, like trying to imagine. what a world would be like if p equal then p. I like that imagination exercise that Lance did. 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 Mertons and Moore, I think.

So this is still not. you know, very technical, but a lot, but it is a textbook, right? Yeah. And then, of course, Sipzer's introduction to the theory of computation is like

a fairly concise and very well written textbook. Yeah. 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? 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. 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 um that 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 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 um yeah like um another thing i think is uh 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. 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 need to be coasting here? Like, do I need to? And yeah, I think, like in research for me, I was always reevaluating, like, okay, you know, what I do last year and what I do the year before. And, you know, like, what do I know now that I didn't know then? And, like, you know, am I progressing? I think, 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, there just isn't such a metric. So all you can really do is evaluate your past self with your present self and compare and contrast to see if you're making progress with whatever it is you want to do. Thank you so much for your time for Professor Williams. I really appreciate it. Yeah, I appreciate you having me here. It's been fun. Thanks. 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 Brooker,

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, 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.