From Schneier on Security
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration
…
B. Schneier| February 29, 2024
Result of the year goes to
Oracle Separation of BQP and PH by Ran Raz and Avishay Tal
which we wrote about in June. This work solves one of the original openQuanta...Lance Fortnow From Computational Complexity | December 31, 2018 at 07:25 AM
A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least...Lance Fortnow From Computational Complexity | December 26, 2018 at 08:31 AM
Here's an open question that goes back to a 2003 paper that I wrote with Steve Fenner, John Rogers and Ashish Naik. The conference paper goes back to 1996.
In...Lance Fortnow From Computational Complexity | December 13, 2018 at 09:53 AM
Today is the national day of mourning for George Herbert Walker Bush, one of the best presidents for science and computing. He created PCAST, the President's...Lance Fortnow From Computational Complexity | December 5, 2018 at 09:03 AM
H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end...Lance Fortnow From Computational Complexity | November 28, 2018 at 01:27 PM
I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll...Lance Fortnow From Computational Complexity | November 15, 2018 at 11:59 AM
With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities...Lance Fortnow From Computational Complexity | November 8, 2018 at 09:00 AM
In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs....Lance Fortnow From Computational Complexity | November 1, 2018 at 06:33 AM
Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially...Lance Fortnow From Computational Complexity | October 25, 2018 at 07:24 AM
Imagine the following not-so-unrealistic scenario: The US-China trade war deepens leading to a cold war. The US blocks all Chinese citizens from graduate school...Lance Fortnow From Computational Complexity | October 18, 2018 at 09:23 AM
As we do every year at this time, we help you find that perfect academic job. So who's hiring in CS this year? Perhaps we should instead follow the advice of John...Lance Fortnow From Computational Complexity | October 11, 2018 at 09:27 AM
Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typecast.
Bill: Always a good...Lance Fortnow From Computational Complexity | October 1, 2018 at 05:06 PM
Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.
Bill: Neither do you. But seriously, why do you...Lance Fortnow From Computational Complexity | September 27, 2018 at 02:44 AM
Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity...Lance Fortnow From Computational Complexity | September 25, 2018 at 02:32 AM
Recently I talked with Ehsan Hoque, one of the authors of the ACM Future of Computing Academy report that suggested "Peer reviewers should require that papers and...Lance Fortnow From Computational Complexity | September 20, 2018 at 08:19 AM
Often when the question comes to what happens if P = NP, one typically hears the response that it kills public-key cryptography. And it does. But that gives the...Lance Fortnow From Computational Complexity | September 13, 2018 at 08:08 AM
Glencora Borradaile wrote a blog post in June about how conferences discriminate.
Let me spell it out. In order to really succeed in most areas of computer science...Lance Fortnow From Computational Complexity | September 6, 2018 at 09:01 AM
The Simons Institute at Berkeley has two semester long programs this fall, Lower Bounds on Computational Complexity and Foundations of Data Science. The beginning...Lance Fortnow From Computational Complexity | August 30, 2018 at 09:25 AM
Katherine Johnson is celebrating her 100th birthday today. This is the first centenary post we've done for a living person.
The movie Hidden Figures made her story...Lance Fortnow From Computational Complexity | August 26, 2018 at 08:57 AM
A couple of years ago, Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is if you choose each string...Lance Fortnow From Computational Complexity | August 23, 2018 at 09:23 AM