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
Many of you have heard of Russell Impagliazzo's five worlds from his 1995 classic A personal view of average-case complexity In short
Algorithmica: P = NP orHeuristica...Lance Fortnow From Computational Complexity | December 16, 2020 at 09:59 AM
In the fall of 1983 as a junior at Cornell I took CS 481, Introduction to the Theory of Computing, from Juris Hartmanis. Needless to say this was the course that...Lance Fortnow From Computational Complexity | December 9, 2020 at 12:55 PM
Back in 2005, I wrote a post titled Chess and Poker. Not really comparing the two but noting that Chess had lost its mojo while poker had high-stakes prime time...Lance Fortnow From Computational Complexity | December 3, 2020 at 09:48 AM
Vaughan Jones, one of the greatest mathematicians from New Zealand, passed away on September 6 at 67. Jones is an expert in knot theory among other areas and received...Lance Fortnow From Computational Complexity | November 19, 2020 at 11:56 AM
Lance: Perhaps we should do a post-election vidcast--what does it mean for complexity!Bill: Not sure if you are serious- but I doubt a Biden presidency will either...Lance Fortnow From Computational Complexity | November 12, 2020 at 10:07 AM
My annual fall jobs posts, giving advice to PhDs looking for faculty positions, were getting repetitive. See last year's post for the usual stuff and feel freeTaulbee...Lance Fortnow From Computational Complexity | October 28, 2020 at 06:27 PM
The Public Broadcasting Service (PBS) launched fifty years ago this month in the United States. The New York Times talks about its fifty reasons how the network...Lance Fortnow From Computational Complexity | October 15, 2020 at 09:00 AM
Everything pre-covid seems at least five years ago to me, so it's hard to believe that MIP* = RE is a 2020 result. To remind you, consider the model where we have...Lance Fortnow From Computational Complexity | October 5, 2020 at 08:50 AM
FOCS 2000 took place in Redondo Beach, just south of Los Angeles, November 12-14. Certainly some great results such as the Reingold-Vadhan-Wigderson Zig-Zag Graph...Lance Fortnow From Computational Complexity | September 23, 2020 at 05:33 PM
Great news out of the Simons Institute.The Simons Foundation has ensured a second decade of research and innovation for the Simons Institute for the Theory ofcollection...Lance Fortnow From Computational Complexity | August 13, 2020 at 10:10 AM
The Complexity Complexity Conference, the conference that shares its name and URL with this blog, originally scheduled for Saarbrücken will be held virtually next...Lance Fortnow From Computational Complexity | July 24, 2020 at 12:21 PM
Guest post by Varsha Dani.My 11-year-old child received a letter in the mail. "Send a book to the first person named," it said, "then move everyone's name up the...Lance Fortnow From Computational Complexity | June 18, 2020 at 09:57 AM
The Computational Complexity Conference has announced the accepted papers for the 2020 now virtual conference. Check them out!
Speaking of the complexity conference...Lance Fortnow From Computational Complexity | May 11, 2020 at 10:41 AM
Bill and Lance have another socially-distanced vidcast, this time with Lance telling the story of two conferences (ACM Economics and Computation and the Game Theory...Lance Fortnow From Computational Complexity | May 7, 2020 at 10:28 AM
As a complexity theorist I often find myself far more intrigued in what we cannot compute than what we can. In 2009 I posted on some predictions of the spread of...Lance Fortnow From Computational Complexity | May 1, 2020 at 10:40 AM
Both STOC and Complexity have announced they will go virtual for the summer. ICALP moved from Beijing to Stuttgart to online. I expect every major summer conference...Lance Fortnow From Computational Complexity | April 20, 2020 at 09:57 AM
Guest post by the TCS4F initiative
(Antoine Amarilli, Thomas Colcombet, Hugo Férée, Thomas Schwentick)
TCS4F is an initiative by theoretical computer scientists...Lance Fortnow From Computational Complexity | April 15, 2020 at 09:42 AM
Since March 19th I have worked out of home. I've had virtual meetings, sometimes seven or eight a day, on Zoom, Bluejeans, Google Hangouts, Google Meet, Blackboard...Lance Fortnow From Computational Complexity | April 2, 2020 at 03:20 PM