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

source: green

“This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.

Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the “sensitivity” of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And “query complexity” calculates how many input bits you have to ask about before you can be sure of the output.

Also: https://www.scottaaronson.com/blog/?p=4229

Paper: https://arxiv.org/abs/1907.00847

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

A tamer version of the superpermutation bound story, now that we’ve had a chance to catch our breath.

The Zoomable Universe, a new book by the astrobiologist Caleb Scharf, the illustrator Ron Miller and 5W Infographics, tours the universe’s 62 orders of magnitude.

Selected illustrations and lightly edited excerpts from The Zoomable Universe follow.

Class numbers, groups, and counting symmetries.

Physicists are closing the door on an intriguing loophole around the quantum phenomenon Einstein called “spooky action at a distance.”

Physicists have failed to find disintegrating protons, throwing into limbo the beloved theory that the forces of nature were unified at the beginning of time.

Super-K’s latest analysis finds that the subatomic particles must live, on average, at least 16 billion trillion trillion years

Kind of a long time.

We really are living in a hologram. Of entangled qubits.

organisms that use bioluminescence in courtship had significantly more species, and faster rates of species accumulation, than closely related organisms that do not use light.

Among other fun facts.

Math is hard, let’s shoot protons.