2020's Biggest Breakthroughs in Math and Computer Science

For mathematicians and computer scientists, 2020 was full of discipline-spanning discoveries and celebrations of creativity. We'd like to take a moment to recognize some of these achievements.

1. A landmark proof simply titled “MIP* = RE" establishes that quantum computers calculating with entangled qubits can theoretically verify the answers to an enormous set of problems. Along the way, the five computer scientists who authored the proof also answered two other major questions: Tsirelson’s problem in physics, about models of particle entanglement, and a problem in pure mathematics called the Connes embedding conjecture.

2. In February, graduate student Lisa Piccirillo dusted off some long-known but little-utilized mathematical tools to answer a decades-old question about knots. A particular knot named after the legendary mathematician John Conway had long evaded mathematical classification in terms of a higher-dimensional property known as “sliceness.” But by developing a version of the knot that yielded to traditional knot analysis, Piccirillo finally determined that the Conway knot is not “slice.”

3. For decades, mathematicians have used computer programs known as proof assistants to help them write proofs — but the humans have always guided the process, choosing the proof’s overall strategy and approach. That may soon change. Many mathematicians are excited about a proof assistant called Lean, an efficient and addictive proof assistant that could one day help tackle major problems. First, though, mathematicians must digitize thousands of years of mathematical knowledge, much of it unwritten, into a form Lean can process. Researchers have already encoded some of the most complicated mathematical ideas, proving in theory that the software can handle the hard stuff. Now it’s just a question of filling in the rest.

[ilovecomputers]

Cracks me up that a mathematician found it ridiculous that a knot problem was unsolved for a decade, so she just solves it in a weekend. What a flex

[HenryYuen]

Just wanted to provide a clarification on the first segment (I'm one of the authors of the result). Contrary to a popular misconception about MIP* = RE: quantum computers CANNOT solve the Halting problem (and it's known that they cannot). Our result is not about SOLVING the Halting problem: instead it says that it's possible for quantum provers who already know the solution to use entanglement to CONVINCE a classical verifier (personified by the policeman in the video clip) that they know the solution. In other words: without entanglement, the provers are unable to convince the verifier they know the answer, but with entanglement, they can.

--- In more detail ----

The Halting problem is to determine whether a Turing machine (given as input) halts. We know there is no algorithm to determine this. But for any specific Turing machine A, if it does halt, then there is a proof of this fact: namely, it will be the transcript of the program A's execution until it halts (in programming terminology it's the execution trace of the program). So in principle you could convince someone that A halts by showing them this transcript.

However this transcript can be astronomically long, because the A can run for an extremely long time. Is there a way to short-cut this?

MIP* = RE shows that if A does halt, it's possible for quantum provers to convince a verifier that there exists a transcript demonstrating this fact... without showing the entire transcript to the verifier. Instead, the time it takes for the provers to convince the verifier will be independent of the run-time of A.

In a nutshell, it's like this: verifier wants to know if program A halts. These almighty provers, who we assume know the answer, claim "Yes, it does. However it halts after the life of the universe." The verifier says, "well, I don't believe you. Prove it to me right here and now." And the provers, using entanglement, can actually do this (without having to wait until the end of the universe).

Hope this clarifies a bit!

[DavidMcCoul]

Experts thought it was a hard problem, but in fact it was knot.

[aazdu]

Lisa is the absolute Chad : she just flexes on decades of mathematical uncertainty " it's just one knot who cares " then solves it like it's some dumb exercise and is like "yeah here you go look, now can we please move on?"

[mehg]

I hope Lisa never writes math text books.
"Proof: Obvious. Left as an exercise."

[mashanaslidnyk]

I loved the "I don't care about knots" comment 🤣

[jimkennedy]

I love it that the woman thought "This can't be that hard.." and then she solved it! awesome!

[BassHero]

That first one was misleading, if you actually read about the paper (or even the title!) You would realize that the proof actually proved that the set of problems that can be solved by entangled quantum provers is exactly the same as the set of problems that can be solved by turing machines (i.e. that are recursively enumerable)

[LieuantDan]

"You find yourself studying knots anyway." Most underrated comment of Dimensional Physics 2020.

[AbiduddinAhmed]

This video called me dumb in 8 different languages

[blas_de_lezo]

The whole idea of an artificial inteligente solving math is incredible promising. As math advances, the number of people expert at the highest level in multiple fields decreases. I believe that if you could somehow posses the current total math knowledge in your brain, some new answers would come up immediatly.

[emberchord]

How is it that everytime a mathematician is interviewed, it is happening in a room that is in utter disarray

[sayantanguha]

"I don't care about knots. haha. I do care about 3-4 dimensional spaces." - spoken like a true Mathematician.

[dirtrockground]

It's so funny that there was a whole issue with the Conway knot and then Lisa comes along saying "I don't understand what is so difficult about this knot, " and then solves the problem.

[Magnasium]

I love this byte sized summary format. You quickly convey the gist of the mathematical problems without it becoming overwhelming for those not familiar with the field. I hope you continue this as a regular series

[nathanthanatos]

quantum computer: *attempts to solve halting problem*

quantum computer: *experiences halting problem*

[brodykrusemark]

The fact that these incredibly smart people exist in the same universe as flatearthers is even more complicated then these math problems

[HealthInspectorz]

I'm a comp sci major, minor in math. I appreciate math since I realized how math and computer science closely tie to each other. The seemingly abstract realm of mathematics somehow finds a way through the machinery of computer science. It's poetic.

[heathispieces]

Lisa is so cool! She was my ta in calculus at ut!

[yimingqu]

All these are really exciting stories, especially the Lean. I've have similar idea and I'm glad to see that someone is working on it and that it might work.