Expanding the Frontier of Verifiable Knowledge in Computer Science
Imagine someone came along and told you that they had an oracle, and that this oracle could reveal the deep secrets of the universe. While you might be intrigued, you’d have a hard time trusting it. You’d want some way to verify that what the oracle told you was true. This is the crux of one of the central problems in computer science. Some problems are too hard to solve in any reasonable amount of time. But their solutions are easy to check. Given that, computer scientists want to know: How complicated can a problem be while still having a solution that can be verified? Turns out, the answer is: Almost unimaginably complicated. In a paper released in April, two computer scientists dramatically increased the number of problems that fall into the hard-to-solve-but-easy-to-verify category. They describe a method that makes it possible to check answers to problems of almost incomprehensible complexity. “It seems insane,” said Thomas Vidick, a computer scientist at the California Institute of Technology who wasn’t involved in the new work. The research …