The expensive simplicity of Daniel Spielman’s mathematics

A mathematician and a computer scientist, Mohan R and Ramanujam R, help us make sense of the fascinating mathematics of Daniel Spielman, a name that turns heads in the math world today. 

UBS Feat images 5

This year’s Breakthrough Prizes, sometimes dubbed the Oscars of science’, were announced on September 22. With a reward of USD 3 million each, these are currently the most lucrative science prize in the world, topping even the Nobel Prizes! This time, eleven researchers were recognised for their discoveries in fundamental physics, life sciences and mathematics. 

Daniel A Spielman won the prize in mathematics for his insights and algorithms that have been significant not only for mathematics, but for highly practical problems in computing, signal processing, engineering, and even the design of clinical trials”. While Spielman’s whole body of work is substantial, one of his achievements caught the special attention of the prize jury and that was his solving of the Kadison-Singer problem, a problem that arose in quantum mechanics but has implications for several other fields. 

Spielman is no stranger to awards. He has won the prestigious Godel Prize not once, but twice, along with his collaborator Shang-Hua Teng. Computer scientist R Ramanujam, who is a faculty member at Azim Premji University, recalls listening to Spielman deliver the plenary lecture at the International Congress of Mathematics at Hyderabad in 2010

During this meet, Spielman was awarded the IMU Abacus Medal (earlier known as the Nevanlinna Prize), which is announced once in four years alongside the Fields Medal. One characteristic of Spielman and his collaborator Shang-Hua Teng is that they generally work on very hard problems. They don’t take up theory building in the abstract, but they focus on some well-known hard problems and work on them. They typically look at the heart of the problem from a different lens.”

Ramanujam marvelled at the fact that Spielman has been part of at least three breakthrough results. This is very unusual. One is good enough for a career! And he has some way to go, so I expect there will be more from him,” he said. 

Equally interested in Spielman’s work — particularly in his solving of the Kadison-Singer problem —is Mohan R, a mathematician and colleague of Ramanujam. Mohan is interested in an area of mathematics called C*-algebra, which is where the Kadison-Singer problem comes from. 

Mohan and Ramanujam combined their expertise and their fondness for communication to break down Spielman’s mathematics for us.

What would you say was Spielman’s first claim to fame? 

Ramanujam: The first was actually his PhD thesis — about error correcting codes (ECC). Say I communicate with you on a channel. Some message reaches you, but how do we make sure that what you got is what I sent? 

What I can do is, send you a code along with the message so that at the receiver’s end, you can do something on the code and check whether it is the right one. The message is after all made of 0s and 1s, right? 

So, say that while sending, one or two bits got flipped, and that code can tell you that has happened. In fact, there is even a way of finding out where it has happened and correcting it. These are called error correcting codes. Spielman did some nice work related to that, which, in retrospect, proved very useful. 

One characteristic of Spielman and his collaborator Shang-Hua Teng is that they generally work on very hard problems. They don’t take up theory building in the abstract, but they focus on some well-known hard problems and work on them. They typically look at the heart of the problem from a different lens.

Daniel Spielman (second from right) with his Nevanlinna Prize, along with the other winners announced at the 2010 International Congress of Mathematicians. 

Source: www​.math​u​nion​.org

Can you tell us about the famous Spielman-Teng partnership?

Ramanujam: Both of Spielman’s Godel Prize-winning works were in collaboration with Shang-Hua Teng, a Chinese-American computer scientist. These two had a collaboration going on for a very long time. 

One was a very nice piece of work called smooth analysis. So, the idea is this: Think of an algorithm — it sits there till some input comes, processes it, and puts out an answer. Now, you want to know how efficient this algorithm is for various kinds of inputs — does it do things fast, are there inputs that make it slow, and others that make it fast, etc. This is called the analysis of an algorithm. 

Then there are optimisation problems. A typical optimisation problem is airline scheduling. Or say the University is trying to build its timetable. There are many people who want to teach courses and many students who want to take them. Somebody has the option of taking one from here, one from there. Coming up with a timetable is usually hard, computationally. It’s difficult to come up with efficient algorithms. 

There is one technique called the simplex optimisation algorithm which has been there since the 70s and has been extensively used. In practice, it works very well. But simplex is terrible with some inputs. Even an undergraduate student can set up a counter example, some input, which will send the algorithm into a tizzy. So, there was always this question with such algorithms which seem to be okay, but theoretically, it is easy to make them look bad. How do you explain this?

Spielman and Teng came up with this idea of smoothed analysis. It says that when you have a method or algorithm, do not just take an arbitrary input and work on it. First smooth” the input a bit, perturb it, then work on it. If there are kinks in the individual inputs that make your algorithm go very fast or very slow, the smoothing will even it out. And then, if your algorithm is really stable, it shouldn’t matter. This is called smoothed analysis. 

This demonstrated that simplex is very efficient and smooth. This work by the duo taught a new technique for a whole field. It was a beautiful piece of work. 

Shang-Hua Teng and Daniel Spielman after they won the Godel Prize in 2008

Source: USCViterbi

Another significant achievement by Spielman and Teng had to do with the good old systems of linear equations. We learn how to solve fundamental problems of linear algebra in school. For example, equations like 5x+3y+6z=72.

But, what happens if you have, say, 50,000 variables and 82,000 equations? Somehow you think that for a computer, it hardly matters. But, all kinds of computational problems appear. Especially if the equations that we’re looking at have some particular mathematical structures like integrals or derivatives — these are linear equations too! 

One particular kind of linear equation called Laplacian equations is of great interest in physics. These are large systems of linear equations which, roughly speaking, involve integrals and derivatives. 

Spielman and Teng came up with a technique for solving such equations. Here too, the word breakthrough’ applies because people had been trying all sorts of things to achieve this. But these two came up with an elegant solution. They call it expensive simplicity. When you wear a dress that looks simple, it’s actually very expensive. It’s a bit like that in mathematics. It is very elegant because it internalises a whole lot of very difficult stuff. 

The jury of the Breakthrough Prize made a special mention of Spielman’s solution to something called the Kadison-Singer problem. What is the Kadison-Singer problem and what’s the big deal about solving it?

Mohan: The origin of this problem comes from quantum mechanics, which is not exactly a field of mathematics. In quantum mechanics, there is a fundamental principle called Heisenberg’s uncertainty principle, which says that at the quantum level, we can’t measure the position and momentum of a particle simultaneously in an experiment. 

It is kind of counterintuitive to whatever we can do in classical mechanics — meaning, in real life. This raises an interesting question — how can we describe the state of such a particle that can be verified experimentally? 

Then in the 1930s or so, Paul Dirac suggested that to describe the state of a physical system, you don’t have to worry about things you can’t measure and look at the things that you can measure. This means that despite the uncertainty principle, there is a way to describe the state of a physical system.

This was a time when mathematicians were trying to write quantum mechanics in the language of mathematics. They were trying to find out the mathematical foundation of quantum mechanics to explain the very counterintuitive stuff happening there. This brought about the birth of a field of mathematics called C*-algebra.

In 1959, Kadison and Singer wanted to check if Dirac’s claim can be verified mathematically and translated the claim into mathematical language. This came to be known as the Kadison-Singer problem. 

It’s not just about solving this particular problem but using the techniques developed in one and translating it into other areas. I think that’s one of the greatest contributions when it comes to solving big problems like these.

What makes this problem interesting is the fact that it’s connected to a lot of different theories. In 2006, there was an article that talks about equivalent versions of the Kadison-Singer problem in 12 different areas ranging from Hilbert space theory, Banach space theory, frame theory, harmonic analysis, time-frequency analysis, computer science, and more. What this means is that if you solve it in one area, simultaneously you solve the equivalent problems in many different areas.

This is a sign that this is a fundamental problem. It’s not just about solving this particular problem but using the techniques developed in one and translating it into other areas. I think that’s one of the greatest contributions when it comes to solving big problems like these. 

How did Spielman manage to solve the problem?

Ramanujam: Mathematicians felt that if there was an answer to this problem, it was probably in the study of algebra. So, they kept trying all kinds of stuff but they were not getting anywhere. Then somebody pointed out that maybe we can think of the Kadison-Singer problem in a combinatorial fashion.

Somehow, I think this caught the attention of Spielman and his students. They worked on this and finally found a solution, and they did it in a different field called graph theory. They thought of it as a network. The question was if you have a network, say a road network with towns, villages and roads connecting them, can you figure out the properties of the network by looking at some parts and sub-networks?

Nikhil Srivastava, Adam Marcus, and Daniel Spielman solved the Kadison-Singer problem, which was originally stated in C*-Algebra, in a totally different field of graph theory. This shocked many people. It was like seeing people who don’t share a language of communicating with each other!

Nikhil Srivastava, Adam Marcus and Daniel Spielman, reportedly on the day they finished writing the proof of the Kadison-Singer problem. 

Source: Yale News

It’s unusual for fundamental maths research to have applications, but in Spielman’s case there has been a lot of buzz about applications. Why is this so, and what applications could there be?

Mohan: Spielman primarily works in algorithms. And algorithms have real-time applications in the sense that you can optimise lots of stuff — make it faster, more precise. Most of the problems he works on are inspired by real-life problems, so if you find a solution, you will have real-life applications. 

Ramanujam: Yes, usually anything which has multiple equivalent formulations like the Kadison-Singer problem has a lot of applications. That tells you that something deep is going on. And when something is so central that it can be said in different ways, and yet it remains a problem… applications are just waiting. 

Now Spielman’s other work like his error-correcting codes has tons of applications. Fundamental communication theory is one, cryptography is another. His work in smoothed analysis is teaching computer scientists how to think. It has provided a new tool in their hands. 

His research on systems of linear equations too has huge applications, because linear algebra is everywhere. We are talking about large systems of equations, like 10,000 variables! How can you efficiently solve them? I’m sure it could lead to very attractive applications. 

In the last decade, Spielman and his co-authors have been doing very interesting work on randomised controlled trials (RCT). RCTs, as you may know, are used in drug and vaccine testing — we heard a lot about them during the COVID-19 vaccine development.

Is there any ongoing work by Spielman you are following and are excited about?

Ramanujam: In the last decade, Spielman and his co-authors have been doing very interesting work on randomised controlled trials (RCT). RCTs, as you may know, are used in drug and vaccine testing — we heard a lot about them during the COVID-19 vaccine development.

We also need RCTs in many sociological contexts like education — to find out the effectiveness of some method. Now, there are fundamental mathematical questions about such trials. The thing is, it is not a good thing to do it in a genuinely random fashion because sometimes, you want to bias the sample. You want to ensure that certain aspects are given the extra importance they need.

For instance, maybe with the testing of a certain drug, you have to give extra importance to women of a particular age, right? So, the challenge, to put it in a crude way, is how to bias your samples and yet get good randomised control trials.

This is what Spielman calls artfully random’. That’s a beautiful term. Is there such a thing? Yet again, his team is attacking another hard problem. I would say that’s the next Breakthrough Prize waiting for them. They don’t have any kind of dramatic results, yet, as they did with smoothed analysis, Kadison-Singer, or any of those. But I would say it’s a matter of time.

Watch Mohan R elaborate on why the Kadison Singer problem is a big deal:

References

About the Author

Nandita Jayaraj is a Science writer and Communications Consultant at Azim Premji University.

Know more about the BSc Mathematics undergraduate programme here: