Landmark Computer Science Proof Cascades Through Physics and Math | Computational Complexity - Quanta Magazine

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

https://d2r55xnwy6nx47.cloudfront.net/uploads/2020/03/Connes-2880x1620_v2.mp4

In 1935, Albert Einstein, working with Boris Podolsky and Nathan Rosen, grappled with a possibility revealed by the new laws of quantum physics: that two particles could be entangled, or correlated, even across vast distances. The very next year, Alan Turing formulated the first general theory of computing and proved that there exists a problem that computers will never be able to solve.
These two ideas revolutionized their respective disciplines. They also seemed to have nothing to do with each other. But now a landmark proof has combined them while solving a raft of open problems in computer science, physics and mathematics...

“The ideas all came from the same time. It’s neat that they come back together again in this dramatic way,” said Henry Yuen of the University of Toronto and an author of the proof, along with Zhengfeng Ji of the University of Technology Sydney, Anand Natarajan and Thomas Vidick of the California Institute of Technology, and John Wright of the University of Texas, Austin. The five researchers are all computer scientists.

Close-up photos of computer scientists A, B, C, D and E
Photo: (Yuen) Andrea Lao; (Vidick) Courtesy of Caltech; (Ji) Anna Zhu; (Natarajan) David Sella; (Wright) Soya Park 

A Cascade of Consequences
In their new paper, the five computer scientists prove that interrogating entangled provers makes it possible to verify answers to unsolvable problems, including the halting problem. 
Read more...

Source: Quanta Magazine