Decades-Old Computer Science Conjecture Solved in Two Pages

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/ [www.quantamagazine.org]

2019-07-26 03:04

tags:
compsci
math
paper

> “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

Mystery Math Whiz and Novelist Advance Permutation Problem

https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/ [www.quantamagazine.org]

2018-11-11 05:04

tags:
math

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

https://www.quantamagazine.org/a-tour-of-the-zoomable-universe-by-caleb-scharf-and-ron-miller-20171106/ [www.quantamagazine.org]

2017-11-11 22:22

tags:
book
photos
physics
space

> 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

https://www.quantamagazine.org/20170302-class-numbers-and-the-symmetries-of-groups/ [www.quantamagazine.org]

2017-03-04 20:42

tags:
article
ideas
math

Class numbers, groups, and counting symmetries.

Experiment Reaffirms Quantum Weirdness

https://www.quantamagazine.org/20170207-bell-test-quantum-loophole/ [www.quantamagazine.org]

2017-02-09 15:29

tags:
physics

> 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

https://www.quantamagazine.org/20161215-proton-decay-grand-unification/ [www.quantamagazine.org]

2016-12-16 00:28

tags:
article
physics

> 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

https://www.quantamagazine.org/20161201-quantum-gravitys-time-problem/ [www.quantamagazine.org]

2016-12-03 17:09

tags:
physics
space

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

In the Deep, Clues to How Life Makes Light

https://www.quantamagazine.org/20161201-how-life-makes-light-bioluminescence/ [www.quantamagazine.org]

2016-12-02 04:21

tags:
article
biology
chemistry

> 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

https://www.quantamagazine.org/20161115-strange-numbers-found-in-particle-collisions/ [www.quantamagazine.org]

2016-11-17 00:40

tags:
article
history
math
physics

Math is hard, let’s shoot protons.