A DECADES-OLD COMPUTER SCIENCE PUZZLE WAS SOLVED IN TWO PAGES

WIRED | 8/4/2019 | Erica Klarreich
Level 3
Click For Photo: https://media.wired.com/photos/5d436fff01669900088ef59f/191:100/pass/Science_Quanta_TA.jpg

A paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This “sensitivity” conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet.

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research develop­ments and trends in mathe­matics and the physical and life sciences.

Conjecture - Problems - Combinatorics - Computer - Science

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

The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them “the bricks and mortar of whatever you’re doing in computer science,” said Rocco Servedio of Columbia University.

Years - Computer - Scientists - Ways - Complexity

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...
(Excerpt) Read more at: WIRED
Wake Up To Breaking News!
Tagged:
Sign In or Register to comment.

Welcome to Long Room!

Where The World Finds Its News!

Categories