{"id":94433,"date":"2019-08-04T18:02:38","date_gmt":"2019-08-05T01:02:38","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2019\/08\/a-decades-old-computer-science-puzzle-was-solved-in-two-pages"},"modified":"2019-08-04T18:02:38","modified_gmt":"2019-08-05T01:02:38","slug":"a-decades-old-computer-science-puzzle-was-solved-in-two-pages","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2019\/08\/a-decades-old-computer-science-puzzle-was-solved-in-two-pages","title":{"rendered":"A Decades-Old Computer Science Puzzle Was Solved in Two Pages"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/a-decades-old-computer-science-puzzle-was-solved-in-two-pages2.jpg\"><\/a><\/p>\n<p>A <a class=\"\" data-event-click=\"{\u201celement\u201d:\u201d ExternalLink\u201d,\u201d outgoingURL\u201d:\u201d https:\/\/arxiv.org\/abs\/1907.00847\u201d}\" href=\"https:\/\/arxiv.org\/abs\/1907.00847\" rel=\"nofollow noopener noreferrer\" target=\"_blank\">paper posted online<\/a> this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This \u201csensitivity\u201d 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 <a class=\"\" data-event-click=\"{\u201celement\u201d:\u201d ExternalLink\u201d,\u201d outgoingURL\u201d:\u201d\n<a href=\"https:\/\/twitter.com\/BooleanAnalysis\/status\/1145837576487612416\">https:\/\/twitter.com\/BooleanAnalysis\/status\/1145837576487612416<\/a><br \/>\n\u201d}\" href=\"https:\/\/twitter.com\/BooleanAnalysis\/status\/1145837576487612416\" rel=\"nofollow noopener noreferrer\" target=\"_blank\">single tweet<\/a>.<\/p>\n<p>\u201cThis conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,\u201d wrote <a class=\"\" data-event-click=\"{\u201celement\u201d:\u201d ExternalLink\u201d,\u201d outgoingURL\u201d:\u201d https:\/\/www.cs.utexas.edu\/directory\/scott-aaronson\u201d}\" href=\"https:\/\/www.cs.utexas.edu\/directory\/scott-aaronson\" rel=\"nofollow noopener noreferrer\" target=\"_blank\">Scott Aaronson<\/a> of the University of Texas, Austin, in a <a class=\"\" data-event-click=\"{\u201celement\u201d:\u201d ExternalLink\u201d,\u201d outgoingURL\u201d:\u201d https:\/\/www.scottaaronson.com\/blog\/?p=4229\u201d}\" href=\"https:\/\/www.scottaaronson.com\/blog\/?p=4229\" rel=\"nofollow noopener noreferrer\" target=\"_blank\">blog post<\/a>. \u201cThe list of people who tried to solve it and failed is like a who\u2019s who of discrete math and theoretical computer science,\u201d he added in an email.<\/p>\n<p>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 \u201cthe bricks and mortar of whatever you\u2019re doing in computer science,\u201d said <a class=\"\" data-event-click=\"{\u201celement\u201d:\u201d ExternalLink\u201d,\u201d outgoingURL\u201d:\u201d http:\/\/www.cs.columbia.edu\/~rocco\/\u201d}\" href=\"http:\/\/www.cs.columbia.edu\/~rocco\/\" rel=\"nofollow noopener noreferrer\" target=\"_blank\">Rocco Servedio<\/a> of Columbia University.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 \u201csensitivity\u201d 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. [\u2026]<\/p>\n","protected":false},"author":396,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,2229,224],"tags":[],"class_list":["post-94433","post","type-post","status-publish","format-standard","hentry","category-computing","category-mathematics","category-science"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/94433","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/396"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=94433"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/94433\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=94433"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=94433"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=94433"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}