Decades-Old Computer Science Conjecture Solved in Two Pages
> “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.
> Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
Mystery Math Whiz and Novelist Advance Permutation Problem
A tamer version of the superpermutation bound story, now that we’ve had a chance to catch our breath.
From the Edge of the Universe to the Inside of a Proton
> 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.
New Number Systems Seek Their Lost Primes
Class numbers, groups, and counting symmetries.
Experiment Reaffirms Quantum Weirdness
> Physicists are closing the door on an intriguing loophole around the quantum phenomenon Einstein called “spooky action at a distance.”
Grand Unification Dream Kept at Bay
> 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.
Quantum Gravity’s Time Problem
We really are living in a hologram. Of entangled qubits.
In the Deep, Clues to How Life Makes Light
> 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.
Strange Numbers Found in Particle Collisions
Math is hard, let’s shoot protons.