How Can Math Protect Our Data?

Every time data travels — from smartphones to the cloud, or across the vacuum of space — it relies on a silent but vigilant guardian in the form of error-correcting codes. These codes, baked into nearly every digital system, are designed to detect and repair any errors that noise, interference or cosmic rays might inflict. In this episode of The Joy of Why, Stanford computer scientist Mary Wootters joins co-host Steven Strogatz to explain how these codes work, and why they matter more than ever. Wootters discusses the evolving list of codes that keep modern communication resilient, and the frontiers in which error correction may have a crucial role, including distributed cloud systems, quantum computing and even DNA-based data storage.

• 0:00Speaker 00

  Hi, I'm Terry Tao. My new book, Six Math Essentials, explores six concepts that have guided mathematicians like me throughout history. With a simple introduction to numbers, algebra, geometry, probability, analysis, and dynamics, I share how these ideas helped me think mathematically and can help everyone better understand our complex world. Mathematics isn't magic. It's a way of thinking anyone can learn. Please visit quantobooks.org to learn more.

• 0:31Speaker 01

  I'm Steve Strogatz.

• 0:32Speaker 02

  And I'm Janna Levin.

• 0:34Speaker 01

  And this is The Joy of Why, a podcast from Quantum Magazine, exploring some of the biggest unanswered questions in math and science today. Hi there, Jana.

• 0:44Speaker 02

  Hey.

• 0:45Speaker 01

  How's it going?

• 0:46Speaker 02

  Good. What do you have for me today?

• 0:49Speaker 01

  Well, we're more or less about the same age, so I'm guessing you remember what CDs are.

• 0:54Speaker 02

  Oh, yeah.

• 0:55Speaker 01

  The kids don't necessarily know. I guess some of them are using vinyl now, aren't they, records?

• 1:00Speaker 02

  Back to vinyl.

• 1:01Speaker 01

  Yeah.

• 1:01Speaker 02

  Nobody's back to CDs, though. I don't think anyone's, like, got a new CD Walkman, you know?

• 1:07Speaker 01

  But do you remember back when CDs were the thing and people would demonstrate that you could scratch them and they would still play?

• 1:14Speaker 02

  Yeah.

• 1:15Speaker 01

  I'm bringing it up because the fact that when you play a CD that's been mangled, if not too totally messed up, it'll still play, is because of a wonderful technology called error correcting code that was built into that kind of device. And that was the first time I ever ran across the concept, but apparently it's really out there in our modern world today. When you're streaming TV shows or cell phones, probably this communication we're having with each other right now, there are probably error correcting codes running behind the scenes, making sure that all our bits, you know, our zeros and ones are getting where they're supposed to be, even though there's always noise. Think how weird it would be if your light switch suddenly switched itself off.

• 1:57Speaker 01

  That doesn't really happen in our everyday macroscopic world, but apparently there's a lot of things that can cause bits to flip, like ones become zeros when they shouldn't. They get hit by a cosmic ray. Or your cellphone signal is bouncing off the walls and it can interfere with itself.

• 2:12Speaker 02

  Hmm.

• 2:13Speaker 01

  But you have to add more bits to help correct the inevitable errors caused by all the noise and all the potential sources of corruption in the environment. And so error correcting codes is the story of math fighting noise. How to use those extra bits as efficiently as possible using redundancy, but in very clever ways.

• 2:33Speaker 02

  And would this be a computer scientist's arena?

• 2:36Speaker 01

  Yeah, totally. That's totally their bailiwick. They're very ingenious. This is a lot of discreet, really clever stuff about algebra, about graph theory.

• 2:48Speaker 02

  Hmm. And do they ever get it really wrong? Do they ever make the errors worse?

• 2:52Speaker 01

  Do the error correcting people need to be corrected?

• 2:55Speaker 02

  Right.

• 2:56Speaker 01

  Well, from what I hear, some of the error correcting codes can recover messages in astonishing ways. But maybe we should dive in.

• 3:05Speaker 02

  Yeah.

• 3:05Speaker 01

  And let Mary Wootters, an assistant professor in electrical engineering and computer science at Stanford, tell us a little bit about the grand story of error correcting codes.

• 3:21Speaker 01

  Hi, Mary.

• 3:21Speaker 03

  Hi, Steve. Thanks so much for having me.

• 3:23Speaker 01

  I'm very happy to meet you and see you here. I was wondering a little bit about this book of yours that you wrote with your co-author Aviad about Algorithms for Toddlers. You want to tell us a little bit about that?

• 3:38Speaker 03

  Sure. Algorithms for Toddlers is a whole semester of undergraduate algorithms condensed into 14 illustrated pages with rhyming couplets, which you can find, I would like to say, at all fine bookstores, but actually just online at barnesandnoble.com because we self-publish. So if that is for you or for your inner toddler, yeah, it's a good thing.

• 3:56Speaker 01

  I enjoyed the few bits of it that I saw on YouTube.

• 3:59Speaker 03

  That's right. Yeah, I have my best kindergarten teacher voice on if you want to see me reading the book on YouTube.

• 4:03Speaker 01

  Do you have an illustrator or did one of you illustrate it?

• 4:06Speaker 03

  I illustrated it.

• 4:07Speaker 01

  You illustrated it.

• 4:08Speaker 03

  So this is a book co-authored with my colleague here at Stanford, Aviad Rubenstein. Aviad and I both occasionally teach the undergraduate algorithms course here at Stanford. And Aviad has young kids, and so he thought it might be a good idea to try to make a book to teach algorithms to them.

• 4:24Speaker 01

  I see. You do seem to have some passion for helping convey the wonders of computer science, of algorithms, coding, to a pretty broad audience. I mean, you're cornering the toddler market.

• 4:36Speaker 03

  We're going where the deishes.

• 4:39Speaker 01

  But so, do you think it's important to share this kind of information in a very broad or accessible way? What's motivating you to do that kind of work? It's not so common.

• 4:50Speaker 03

  That's a good question. I mean, I think you're right. This is something that I really care about. I get really excited about my work, about the mathematical and technical ideas in it, and want to share the joy. I want to communicate that to others. So I think that's where that comes from in me is basically there's like this little five-year-old kid inside being like, oh, my God, it's so cool.

• 5:10Speaker 01

  Beautiful. That's an honest answer. Well, so we have you with us to talk about error correcting codes, and I would love to dive into that. It's not something I'm very familiar with, and it's possible our listeners are not either. So if you don't mind, I'm wondering, how did you get interested in that? What inspired you to start learning about them?

• 5:30Speaker 03

  Yeah, so maybe just for listeners who have no idea what the heck these things are, error correcting codes are sort of a fundamental tool for protecting data from noise. So basically, whenever you send data, think of your cellphone talking to a cell tower, or if you want to store data on a hard drive or something like that, like errors are going to happen. Radio waves get interfered with, hard disks get scratched, or things go wrong. And so you need to add redundancy, basically, in order to make sure you don't lose data. And an error correcting code is a way to do that. And how did I get into it? One of the things I really like about this area is it's super interdisciplinary. So my background's in math, and there's a lot of really beautiful mathematics that goes on with error correcting codes.

• 6:13Speaker 03

  But now I'm in a computer science department and electrical engineering department. There's also a bunch of folks in CF and EE who think about these things, too, and lots of other communities where error correcting codes are interesting. So I think that's one of the things that really drew me in, is just the people and the opportunity to deploy a wide range of toolkits to study this one type of object.

• 6:30Speaker 01

  Great, okay. You've mentioned a little bit about why error correction is important, that there's always some source of corruption or noise or something. We hear the word noise a lot. I mean, in ordinary speech, noise means I'm talking to someone at a cocktail party and there's other people making noise or there's music. How should we think of noise generally?

• 6:51Speaker 03

  It's a great question, and there's not one answer. But it really depends on the application. So in communication, you have your signal that you want to send and you have lots of other signals that might interfere with it, which is not that different, at least conceptually, with the cocktail party. When things are digitized on either ends, that can be manifested as bit flips, for example. Like, I meant to send a zero and actually a one gets received. Or possibly, you get some kind of uncertainty where you're like, ah, I'm 85% sure it was a one, but it could have been a zero. So that's one sort of model of noise. But you could also have different types of noise depending on the context. So for example, you might have something that's called an erasure rather than an error, which would mean that a bit just turns into a question mark. That would be the formal version of it.

• 7:33Speaker 01

  Sort of like a blank or something? There's nothing there anymore?

• 7:36Speaker 03

  Exactly. For example, in a distributed storage system or something, if a server goes down or if a storage node goes down, you know which one went down, but you still don't know the data on it. So that would be like an erasure type of model. But there are lots of other models. You could have synchronization errors. Like, I'm supposed to receive a string of length seven and I actually receive one of length six.

• 7:55Speaker 01

  Ah.

• 7:56Speaker 03

  I know one bit went missing somewhere, but I don't know where.

• 7:58Speaker 01

  Oh, wow.

• 7:59Speaker 03

  Or the other way around. Things could get inserted in or insertions and deletions. There's really a rich class of errors, and that's kind of what makes this problem very interesting.

• 8:09Speaker 01

  So there's something really mysterious about how you could even possibly do error correction, which is if something is missing, like a one or a zero was supposed to be there, but it's not, or a one got flipped to a zero for whatever reason, how could I possibly know that? What is an error correcting code, I guess, is what I'm asking?

• 8:27Speaker 03

  Great. Yeah, so first, you're totally right. If we don't do anything to the data, there's nothing that can be done. If I'm going to be sending you a random string of zeros and ones and something gets erased and turned into a question mark, you have no hope of learning what that is. But the idea of an error correcting code is that you're going to add a little bit of redundancy to help. And so the most naive way to do this is just to repeat the data a whole bunch of times. And then you'd hope that enough copies are there, that corruptions don't matter too much. And that's works in most situations, but it's extremely costly. If you're talking about communication systems or storage systems or something like that, that's more power, more time, more space. That's not great. And so instead, we use something called error correcting codes to have the same idea, but add a little bit less redundancy. To show

• 9:09Speaker 03

  how this works, maybe I can give a quick toy example illustrating the principle, and then I could talk a little more generally about some geometric intuition behind what's going on here. So as a first example, let's suppose that I want to send you two bits. So A and B, and they're either going to be zero or one. And I know that despite all the effort that we've done to get the sound just right on this podcast and everything, unfortunately, whatever I tell you in the next like 10 seconds, one bit that I tell you is going to get erased, is going to get replaced with a question mark. And so in this setting, if I want to send you two bits, the naive thing to do is to send you four bits total. I'll send you A and B, and then A and B again. And then no matter what gets erased, you'll still get both A and B. For example, I could send you, if you hear A

• 9:52Speaker 03

  question mark A B, well, you still have at least one copy of A and one copy of B, so you know what's going on. Okay, so that's the baseline. That's four bits. But here's a better scheme that I could do. I could send you A and B, and then A plus B mod 2, or AX or B.

• 10:08Speaker 01

  Okay, wait, let's think about that. Go slowly. Let's see why that works.

• 10:11Speaker 03

  So just to give a quick example of A and B were 0 and 1, then I would send you 0 1 1, because A plus B is 1, mod 2 is 1. Or if A and B were both 1, I'd send you 1 1 0, because A plus B is 2, which is 0 mod 2. Right? So I'm going to send you now 3 bits. And why does this work? Well, suppose that one of these bits gets erased, just for the sake of example, say it's the second one. So you hear A question mark, A plus B mod 2. And when you get both of those pieces of information, you can actually figure out what B was meant to be, even though it got erased. If you know that A was 0 and A plus B mod 2 was 1, then you know that B must have been 1.

• 10:54Speaker 03

  That's the only thing that you can add to A to get 1 mod 2. So you can always solve the system to figure out what you are missing.

• 11:01Speaker 01

  I see. And so just in case anyone listening isn't familiar with the idea of mod 2, I guess a simple way to say it would be, is it even?

• 11:10Speaker 03

  Yeah, that's exactly right. So you add those together and you'd say, is it even? If so, that's a 0. If it's odd, that's a 1.

• 11:14Speaker 01

  At the receiving end, am I supposed to know that you're doing this A plus B mod 2? Like, is that understood?

• 11:20Speaker 03

  Great, yes, that is understood. So we've agreed beforehand on what scheme we're going to use.

• 11:24Speaker 01

  OK.

• 11:25Speaker 03

  So this was just a very simple example, but it illustrates that you can do better than sort of the naive repetition. Real error correcting codes are generally much bigger than this, but there's a big class called linear error correcting codes, which have basically this idea. So you start with your message. Let's say instead of 2 bits, I have k bits, and I want to add some redundancy. The redundancy that I add is by taking parity checks of my message. So instead of taking all of them mod 2, that's one parity check, but I could also take the first plus the third plus the seventh mod 2.

• 11:58Speaker 01

  Oh, wow.

• 11:59Speaker 03

  And the seventh plus the eighth plus the ninth mod 2, and so on. And the game is kind of how do you design these parity checks so that at the end of the day, you can correct against the flavor of error that you're interested in, be that erasures or errors or synchronization errors or other sorts of things? Here's a geometric way to think about this previous example. So what's going on? There are four possible messages that I might want to send to you. There's 00, 01, 10, or 11. And correspondingly, there's four possible strings that I might send to you. These are now 3-bit strings. So I might send you 00, 01, 1, 10, 1, or 11, 0. Those are the allowable strings in this silly example, OK? So now I've got these four strings of length 3.

• 12:45Speaker 03

  These four special strings that I just said, they have the property that they all differ from each other in at least 2 places. So it takes 2 bit flips to get from one to the other.

• 12:55Speaker 01

  Oh, that's nice. OK, this is helpful.

• 12:57Speaker 03

  Right. And so What I've just done here is I've designed a set of strings so that they all differ in at least two places. And we can see why this means that they can correct one erasure. And you can generalize this to talk about errors as well. So instead of something getting replaced with a question mark, I would have like a zero getting replaced with a one or a one getting replaced with a zero, but I don't know where. But if I have such a design of strings, all three apart, I can actually correct one bit flip error.

• 13:26Speaker 01

  Hmm. So you could put in a lot of redundancy, but then you're not sending much message. Right. Tell us how you would characterize the trade off.

• 13:33Speaker 03

  So there's many, many things that one could care about, but a key trade off that one cares about here is this notion of distance. So how far apart are my special strings in terms of bit flip error? And then also, how many strings are there, given the length of the string? I only get to say one message per string. So the more strings there are, the more messages I get to send.

• 13:56Speaker 01

  Okay, that's a nice way to say it.

• 13:57Speaker 03

  So let's say I'm going to have a bunch of strings of length, I don't know, 100, right? And I want them all to be at least 10 apart from each other. I want to be able to correct at least four errors or something like that. Then the more length 10 binary strings that I can fit in while never making any pair of them too close to each other, the more efficient that code is, basically, the more expressive my language is.

• 14:24Speaker 01

  It occurs to me, though, maybe this is trouble with a mathematician talking to another mathy person, that we may want to back up for a second and just go a little more palpable. As a grad student, I remember someone showing me a CD. I don't know if our listeners even remember what CDs are, but it was a big deal back then to take a coin or something and scratch the CD. And then unlike vinyl records, you didn't hear it. The CD player would take care of it somehow.

• 14:52Speaker 03

  That is almost certainly something called Reed-Solomon error correction, which is very pretty stuff based on polynomials. That is a perfect example of error correction at work.

• 15:01Speaker 01

  Uh huh. And do you have some others for us? I mean, if I'm watching some TV show or movie, are they doing error correction when they send it to me?

• 15:09Speaker 03

  Yeah, basically, anywhere where data is stored or transmitted today, there's going to be error correction. There are also other things you can do on top, like for Netflix or something, like they're trying to send you these relatively big packets or something. So if a packet doesn't come through, your computer will just say, hey, I didn't get that packet, and they can send it again or something. I should also say, I'm not an expert on streaming video. I don't know exactly how that works, but that's my understanding. But yeah, there is error correction at some level, basically anywhere data is communicated or stored. So CDs are a great example, cell phone communication, satellite communication. It's actually very interesting. Error correcting codes are just a very useful sort of combinatorial and algorithmic primitive. They have uses in algorithm design. They have uses in complexity theory, in theoretical computer science, pseudorandomness,

• 15:54Speaker 03

  things like that.

• 15:55Speaker 01

  Well, you've mentioned some error correcting codes by name already. Is there sort of a broad category of codes that we should know about other than those?

• 16:04Speaker 03

  Yeah, so there are lots and lots of different types of error correcting codes out there. One family is algebraic. I mentioned Reed-Solomon codes earlier. This would fit into that family. So algebraic codes are codes that are mostly based on polynomials over finite fields. So that's some jargon. But the basic idea is if our goal is to come up with a whole bunch of strings that don't agree with each other too much. And imagine I were to come up with a big set of such strings by taking a whole bunch of quadratic polynomials and evaluating them at a bunch of points. And these are going to give me a bunch of strings. In this example, it's strings of real numbers, 1, 2, 3, 4, 5, 6, 7, 8, and so on. And then I might ask, well, OK,

• 16:49Speaker 03

  how far apart are these strings from each other? Well, any two quadratic polynomials can only intersect in two points. You can kind of see this for yourself if you like, imagine trying to draw parabolas and like, how many points can you get them to intersect in? It's no more than two. So that means that if I were to build a bunch of strings this way, they can't agree in more than two points.

• 17:08Speaker 01

  I see. That's a nice picture.

• 17:10Speaker 03

  And so that's the basic idea that's at the core of a lot of these algebraic constructions. Another family is what I would call graph-based codes. So these are codes that are based on bipartite graphs. And so the idea here is I'm going to view All of the elements of my code words, that is, the elements of these special vectors that I will send. So I'd like, maybe I have a binary string of length n. I'm going to view each one of those n positions as a vertex in a graph. Then I'm going to have a bunch of other vertices, which I'll call check vertices, floating around that are connected to some of these, what's called variable vertices. So the vertices that are indexing positions of my code word.

• 17:54Speaker 03

  And I'm going to say that I need to come up with a big set of binary strings that are all pairwise far apart. The set of strings I'm going to consider are strings so that when I label these n vertices with those numbers, zeros or ones, then all of the other vertices, these check vertices, should always see something nice. Let's say they should always see an even number of ones or something like that. Depending on the types of constraints you put on these extra nodes, you can define a whole lots of classes of codes like this. And then you can use ideas from graph theory to analyze how far apart these strings are from each other. And you can also use that to design efficient algorithms. This is something maybe we haven't talked about so much

• 18:38Speaker 03

  is that you actually don't just want a big set of strings that all fall apart from each other. You also want them to have enough structure so that you can correct errors efficiently with an efficient algorithm. And sometimes these graph-based codes give us very efficient algorithms for doing that.

• 18:51Speaker 01

  OK, so we've got graph-based codes, algebraic codes.

• 18:54Speaker 03

  Yeah, and I think those have been the two big ones for a long time. But relatively recently, there's a new class of codes, which is more information-theoretically motivated, called polar codes. These were invented in 2008, something like that. And these don't maybe quite fit into either of those categories. They're now in wireless standards, and they're very good.

• 19:14Speaker 01

  Does the word polar have any meaning that we can understand? Is it a very technical thing? Or what's polar about it?

• 19:22Speaker 03

  Yes, there's some really great intuition about it. So imagine that I have some noisy channel between you and me, something that's going to introduce some errors. What polar codes utilize is a transformation that basically will transform a whole bunch of channels that are kind of equally not great into a few channels that are fantastic and a few channels that are really, really bad. So that's where polar comes from. It kind of polarizes into having a few really good channels and a few channels that are really not great. And then you just throw away the channels that are really not great and use the really good ones. And that kind of gives you your code.

• 20:02Speaker 02

  Wow. It seems like a big gulf between that, you know, intersecting parabolas and when your friend's trying to tell you the end of their dramatic story from last night.

• 20:13Speaker 01

  Yeah, I have to admit, I mean, this is very far out sophisticated stuff. So can I run a few analogies by you?

• 20:19Speaker 02

  Yeah, please.

• 20:20Speaker 01

  They're not perfect, but I think they might get some of the essence of what she was trying to say. For instance, she mentioned first algebraic codes. So here's my analogy. It's sort of like I'm trying to send you a message and I'm going to do it by sending you a secret math puzzle.

• 20:36Speaker 02

  Okay.

• 20:37Speaker 01

  Okay. The secret puzzle is going to take the form of a function. She mentioned algebraic objects like parabolas, you know, quadratic polynomials. So there's some ingenious way that I can translate my message into a curve. That's already a cool idea, that my message is now going to have a shape. And I'm going to send you a few points on that curve. And then the idea is that even if some of the points get messed up, because there's so much structure built into the way I'm sending it to you, you'll be able to reconstruct the whole curve and thereby recover the intended message.

• 21:09Speaker 02

  Right. That's very helpful. Yeah.

• 21:12Speaker 01

  Let me give you another one. So she mentioned graph-based codes. Okay, the analogy here would be that this is like a group project with a lot of cross-checking. You know, like think of the kids, they have to do group work. Usually they hate it because some kids are loafing, other kids are doing all the work. But here, it's not going to be like that. Each bit, we're going to think of as like a person in the group. And each person's going to work on several parts of the project. And then small subgroups of the whole group are going to compare their answers. So that if one person messes up... That's like an error. Then the group can spot the error and fix it. There's a network structure in the problem that decides who's checking who.

• 21:53Speaker 01

  And through all those interactions, somehow, errors can get corrected collectively.

• 21:58Speaker 02

  It's kind of like the opposite of a game of telephone.

• 22:00Speaker 01

  Something like that.

• 22:03Speaker 02

  Right. That's just a chain and the error just has no way to correct. It just gets worse and worse and worse.

• 22:08Speaker 01

  Yeah.

• 22:08Speaker 02

  But in a more complicated graph, there's a potential for correction. It's interesting.

• 22:12Speaker 01

  That's the idea, that the design of the graph can help you with the error correction. And then the last thing that Mary mentioned was polar codes. Those are pretty deep and modern. As she says, it's only 2008. Those are apparently like close to theoretically optimal. It's like if I have a bunch of junky walkie-talkies and we're going to communicate with those. And there's some magical way to make some of the walkie-talkies fantastically clear and good, while others become totally terrible and useless. And somehow, you then make sure to send your message only over the good ones. Whereas the bad ones, you don't have to throw them away. They turn out to act like fillers for the rest of the structures. They play a sort of supporting role.

• 22:54Speaker 01

  Almost like if you built a complicated bridge, to do a different analogy, where you had some strong beams and some really bad beams. The bad beams are needed to make the whole bridge, but you're not going to put any weight on those. You're only going to drive over the strong beams. It's something like that in the polar codes. You polarize the system into really good and really bad stuff and try to just use the good stuff.

• 23:16Speaker 02

  I'm not driving on that bridge, man, is all I'm saying, though.

• 23:19Speaker 01

  No, it's the best bridge you could be on in the face of noise, turns out.

• 23:24Speaker 02

  Right.

• 23:25Speaker 01

  Anyway, so it's really deep stuff. And we're going to hear more from Mary Wootters after the break about how these ideas get used in things like cloud servers, how they may help in the future for quantum computing, and just how practical it is. So stick around, we'll see you after the break.

• 24:05Speaker 01

  Welcome back to The Joy of Why. We're speaking with Stanford computer scientist Mary Wootters. From a little bit of the preparation I did to talk to you, I got the impression that there are some folks in your field who might think of the whole subject as a little bit old fashioned. Are there people making claims like that? Or what's your take on that?

• 24:26Speaker 03

  Yeah, so error correction has been around since probably late 40s, early 50s. So Richard Hamming, Claude Shannon, and then a whole bunch of other people, you know, sort of foundational in this area. And all of these NASA missions and stuff like that, is there a correction going on there too? In my view, I think error correction is a very classical area, but I think it's also still a very interesting and important area for a couple of reasons. So the first reason is that there are actually a lot of questions that people were asking back in the 50s that we still don't know the answers to. There's been progress on that over the past 75 years or so. There's still very foundational and fundamental questions that are left to be answered. The second reason is that technology changes. And so the types of error correction that was developed in the 50s, or 60s, or 70s,

• 25:11Speaker 03

  or 80s is no longer necessarily the type of error correction that we want today. One big example of this is now that everything is much more distributed, we might care a lot more about the communication costs of our error correction. This is not something that people cared about as much in the 50s.

• 25:27Speaker 01

  Communication between the parts of the distributed system? What would be the example?

• 25:31Speaker 03

  Yeah, so for example, if I want to store something in a distributed storage system, what does that mean? I have my data and it's broken up and sent all over the cloud. And the types of errors that I might be worried about in this context are some storage node goes down. I don't want to lose information if that happens. And traditionally, when such a thing were to happen, if a server were to go down, you'd want to set up a replacement node or something like that. And traditionally, that would involve downloading all of the data from elsewhere in the system, doing the error correction, figuring out what belongs on that node and putting it back there. That's a lot of sort of internal communication within the system. And one thing that Richard's been working on for a little while more recently is schemes

• 26:14Speaker 03

  for doing that whole repair process, but in a low bandwidth way. So a way where the internal nodes don't need to talk to each other all that much.

• 26:21Speaker 01

  So this language of nodes, servers, I'm sure it's very tangible to you, but I'm never exactly sure what people are talking about. So a server is a kind of computer with a particular purpose, or a node is another name. What do these things mean in plain speak?

• 26:38Speaker 03

  What I have in mind here is that you've got a hard drive over here, you've got a hard drive over there, and your data is getting split between those two hard drives. That's sort of the model.

• 26:48Speaker 01

  OK. And so that's something that didn't use to happen when different hard drives didn't talk to each other in the old days. It was just a computer sitting on a desk with a hard drive. And now you're saying a lot of distributed systems, and you refer to the cloud. I'm never exactly sure what the cloud is either. The cloud is what? Lots of computers in different locations? So-called server farms and stuff like that?

• 27:10Speaker 03

  Yeah, that's right. That's the model to have in mind here. So you have lots of different computers, either compute nodes. So these are like computers that are actually doing tasks for you or storage nodes. These are just computers that are storing stuff for you. And you have many of them, and they're all talking to each other.

• 27:25Speaker 01

  So the error correction, then, that is a modern problem that we didn't use to have is dealing with the errors between all the parts of this distributed system as they talk to each other.

• 27:35Speaker 03

  Yeah. Like, if you just forget that they're different computers and imagine they're all the same computer, then this is the same question as before. But now our objective function is a little bit different. I don't just want whatever correction algorithm I'm doing to run fast. I also want it to run fast so that the computers don't have to talk to each other too much, because that sort of intra-system communication is costly, or more costly than it used to be.

• 27:58Speaker 01

  OK. Now, so, given that we're now talking about new challenges or new-ish challenges, one that I'm sure is on the minds of some of our listeners is quantum computing, which we keep hearing about, that that is going to be a real thing sometime soon, and we should be prepared for it. Is there anything really different that we need to think about if we're doing error correction for quantum computing? And also, why would we need to do it for quantum computing?

• 28:28Speaker 03

  Definitely, error correction for quantum computing is a big thing. And at least at the moment, it's arguably much more important than error correction for classical computing, because my understanding is that the implementations we have of quantum computers are very, very noisy. And so it's really important to do error correction. There's a couple of different ways to get such things. One of them is based on classical coding theory. So there's something called a CSS code, which basically you take two classical error correcting codes that have some nice relationship with each other, and you can put them together to correct quantum errors. But then there's other sorts of types of error correction. You know, they're a special thing. I'm not an expert, but I have been thinking about it a little bit.

• 29:11Speaker 03

  It's a really fascinating problem, and I'm getting more and more into it recently. But I would say also, I guess, quantum error correction is another great example. Like, why should we still study error correction in this modern day and age? Didn't we know about it since the 50s? But like, yeah, quantum computers are a great example of a technology that at least we hope will be around fairly soon that certainly wasn't around back then. And there's something called DNA storage, which basically you're using DNA as a storage system. So the idea here is we can synthesize DNA and we can sequence it. So basically, that means we can write and we can read. That allows us potentially to build storage systems out of it. And so the proposed application for such systems would be for very cold storage, so things that you want to store for a very long time, because it is very costly to access.

• 29:56Speaker 03

  You need to sequence some DNA, which is not as fast as reading something from a hard disk. But it is extremely stable and extremely small, so you could archive things for a very long time very efficiently this way. And for this application, like any storage system, you want to design error correction for it. And what sorts of errors do you would expect? Precisely these synchronization errors, like bases drop out or bases get added, depending on the technology that you're using to sequence the DNA.

• 30:21Speaker 01

  Oh, that's an interesting idea. So rather than doing nanotechnology, this is like natural nanotechnology.

• 30:27Speaker 03

  Exactly, yeah.

• 30:28Speaker 01

  Wow. People are seriously thinking about this? I mean, it seems so inaccessible to have stored things in DNA.

• 30:34Speaker 03

  Yeah, not only are people thinking about it, but people had done it. This is definitely possible.

• 30:38Speaker 01

  But what kinds of things would get stored that way?

• 30:40Speaker 03

  Well, any data you could want. So you could store a movie, you could store an image, you could store text files.

• 30:45Speaker 01

  It seems outrageous.

• 30:46Speaker 03

  True. But, well, I mean, so one important thing to note is that this is not like DNA in a living organism. It's not like you're walking around with a library of cotton verse like on your elbow. This is just the molecules, not in a living organism.

• 30:59Speaker 01

  Right. There was a field some years ago that people called DNA computing. So I guess the thinking is we've got this naturally occurring wonderful storage device that evolution has used for probably literally billions of years. So why not use it ourselves?

• 31:16Speaker 03

  Yeah, and it brings up lots of really interesting challenges from the error correction point of view, because we were talking earlier about these sorts of synchronization errors, like the types of errors that are introduced when doing DNA storage are different than the types of errors that you expect in silicon devices or something like that. And you have to designing different codes to deal with them.

• 31:35Speaker 01

  Right. I mean, the biologists know quite a bit about that. Like, we talked earlier about frame shift errors where you might be off by a single base and you're just shifted. A whole string is shifted. But they also have something called interpolation errors, right? Where a wrong base can get wedged in there and split up a string.

• 31:53Speaker 03

  And there are other sorts of constraints as well. Like, you can't just write any old molecule you want or any old string of AGCs and Ts, because some of them will have weird properties. Well, they'll then like kink up back on themselves or things like that. And so there are some constraints also for how you design your code, just based on the biology.

• 32:08Speaker 01

  Well, OK, so you're giving us a pretty good broad survey here of this. And I wonder, when you mentioned the foundational questions that still exist in error correction, theoretically, is that where your heart is? Like, do you like to do the real world part of error correction? Do you like the fundamental theoretical computer science parts of it? What winds your watch?

• 32:30Speaker 03

  I really like these fundamental math questions that sort of remain open, I think, are very important, not just from an error correcting code standpoint, but also just from a mathematical standpoint. But then it's also sometimes nice to... Put on a more applied hat to at least go talk to folks who are actually influencing stuff, both because that means I get to learn new things, which is fantastic. And it also, I think, informs different ways of thinking about these very classical questions. Like, if you get an injection of a new, more applied problem, you're like, "Oh, that is a question I hadn't thought to ask before. It is really interesting." So you can sort of get new fundamental questions that way.

• 33:04Speaker 01

  Uh huh. So we did talk earlier about your book, Algorithms for Toddlers, but I see that you've also designed games, that game about monsters that grew from beans?

• 33:16Speaker 03

  That's true. Yeah, so a project I had with some of my friends from graduate school. It's a puzzle game. It's called Bean and Nothingness.

• 33:24Speaker 01

  Oh, I see. Now I'm getting the joke. Hearing you saying it that way, now I get the joke.

• 33:30Speaker 03

  It's a philosophy pun.

• 33:31Speaker 01

  Ah, being a nothingness. What, is that a Jean-Paul Sartre book or something?

• 33:35Speaker 03

  Yeah.

• 33:36Speaker 01

  Jeopardy question, right there.

• 33:38Speaker 03

  Yeah, so Being and Nothingness is a famous book. Bean and Nothingness, B-E-A-N, is our video game.

• 33:46Speaker 01

  And what's the idea there?

• 33:47Speaker 03

  Well, I think it's a very good puzzle game. Personally, I find it very difficult. The storyline has a little bit to do with being a math graduate student, because we were math graduate students when we started making it. Although, I think it took us nine years to finish, because once we graduated, it dragged out for quite some time. But the basic premise is you get dropped in a puzzle that's totally static, like nothing's going on. You have to get to an end tile, and what you have is a magic wand and some recipes. And the recipes give you ways of turning beans into monsters, which will then act and interact with each other and with you in interesting ways. And they can kill you, but they can also help you in ways like destroying blocks or interacting with each other, or things like this, to help you get to the end. That's pretty separate from my

• 34:30Speaker 03

  academic work, but it's a lot of fun to make. And if your listeners enjoy difficult puzzle games, I would definitely recommend it. I have fun playing.

• 34:37Speaker 01

  Does that kind of playful energy come into your mathematical and scientific work? You mentioned to us that more generally, you have some interest in illustration. But some people think of art and visual things as being kind of holistic, right-brain stuff, whereas very logical reasoning of the type I imagine you need to do in coding theory is kind of left-brain. Maybe that's all bogus. Maybe you don't buy any of that. You're using both halves of your brain all the time, and you don't make that distinction.

• 35:07Speaker 03

  That's a good question. It definitely comes into my work in that the things that I produce in my teaching materials and also in my more academic scholarly work typically has silly illustrations. But when I'm thinking about a problem, I think my first approach is very holistic. And you want to understand the whole picture. You think about new ideas. And then at some point, it's time to sit down and do all the nitty gritty details. But that's the same when you're making a picture or something. For me, at least, there is a time when you have to go down, you have to make all the little lines just right and do the inking and stuff. So to me, it seems like there's both big picture stuff and detail stuff in both types of tasks.

• 35:46Speaker 01

  It does to me, too, that you have to make a mess, and then you have to clean it up.

• 35:50Speaker 03

  Right.

• 35:51Speaker 01

  Or something, right? It's sort of in that sequence. You've mentioned that you like the collaborative aspect of learning new things, how you can import those ideas back to fundamental theory. How would you put it, though? What is it that gives you the most pleasure in your subject?

• 36:06Speaker 03

  Gosh, I'm fortunate that there are many things that bring me joy in my job. The human aspect, I really love. Another aspect is the joy of discovery. Like, solving puzzles is fun. Like, that's enjoyable. But then I think also there's this larger project that all researchers are contributing to the sum of human knowledge, stuff like that. You know, I think some of these problems are important. And even if I can't solve them perfectly, maybe I can make a dent. And that brings me joy as well.

• 36:33Speaker 01

  Well, Mary, it's been a real pleasure to talk to you about error correcting codes. And thanks a lot for joining us today.

• 36:39Speaker 03

  Thanks so much for having me.

• 36:43Speaker 02

  I'm struck how we always come back to the human dimension. Here, in some sense, you're mathematizing human communication in a way that's become so difficult, so challenging, and so abstract. And yet, at the end of the day, it kind of comes back to this human capacity to see things on this large scale and this small scale.

• 37:02Speaker 01

  Uh huh. Is it this desire to play, is that, do you think a productive impulse for a scientist, is it an essential impulse? What do you make of that?

• 37:11Speaker 02

  There's no question that my colleagues will say, hey, you know, it might be really fun to look into, I don't know, something crazy, a non-orientable manifold, whatever, right? This is very common in how scientists talk to each other. You know, I'm not done playing around with how that looks in that spacetime. So I think it's anecdotally a really crucial part of how we interact with the work and why we pursue certain things.

• 37:35Speaker 01

  Yeah, even the word puzzle, I think, is indicative of a spirit. If you think of what you're doing as solving puzzles, that puts you in a childlike frame of mind where it's okay to make a mistake, you can explore. If you think you're doing an important problem, that feels more grown up and starchy.

• 37:53Speaker 02

  I definitely think there's a childlike character to a lot of the scientists I know. And that there, there has to be a moment where you really are just playing in the sandboxes before you can figure out, okay, what's the actual direction to go in?

• 38:05Speaker 01

  Well, as always, Jana, it's a pleasure to hang out and play with you.

• 38:09Speaker 02

  Exactly. Until next time.

• 38:12Speaker 01

  Take care.

• 38:12Speaker 02

  Bye.

• 38:13Speaker 01

  Bye bye.

• 38:19Speaker 02

  If you're enjoying The Joy of Why and you're not already subscribed, hit the subscribe or follow button where you're listening. You can also leave a review for the show. It helps people find this podcast, find articles, newsletters, videos, and more at quantamagazine.org.

• 38:37Speaker 01

  The Joy of Why is a podcast from Quantum Magazine, an editorially independent publication supported by the Simons Foundation. Funding decisions by the Simons Foundation have no influence on the selection of topics, guests, or other editorial decisions in this podcast or in Quantum Magazine. The Joy of Why is produced by PRX Productions. The production team is Caitlin Folds, Livia Brock, Genevieve Sponsler, and Merritt Jacob. The executive producer of PRX Productions is Jocelyn Gonzalez. Edwin Ochoa is our project manager. From Quanta Magazine, Simon France and Samir Patel provided editorial guidance with

• 39:17Speaker 01

  support from Matt Carlstrom, Samuel Velasco, Simone Barr, and Michael Canyungalo. Samir Patel is Quanta's editor in chief. Our theme music is from APM Music. The episode art is by Peter Greenwood and our logo is by Jackie King and Christina Armitage. Special thanks to the Columbia Journalism School and the Cornell Broadcast Studios. I'm your host, Steve Strogatz. If you have any questions or comments for us, please email us at [email protected]. Thanks for listening.