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
The Institute of Science Information (ISI) was founded in 1960 to help index the every growing collection of scientific journals. The founder of ISI, Eugene Garfield...Lance Fortnow From Computational Complexity | January 15, 2015 at 01:34 PM
In 2007, the science historian Martin Campbell-Kelly wrote an article The History of the History of Software, where he writes about how he initially wrote histories...Lance Fortnow From Computational Complexity | January 8, 2015 at 08:28 AM
Theorem of the year goes to 2-Server PIR with Sub-polynomial Communication by Zeev Dvir and Sivakanth Gopi. In Private Information Retrieval you want to accessshowed...Lance Fortnow From Computational Complexity | December 29, 2014 at 01:41 PM
I just received the Cornell Math Matters, dedicated to the memory of Eugene Dynkin who passed away on November 14 at the age of 90. In my freshman year at Cornell...Lance Fortnow From Computational Complexity | December 22, 2014 at 05:33 PM
The NIPS (machine learning) conference ran an interesting experiment this year. They had two separate and disjoint program committees with the submissions split...Lance Fortnow From Computational Complexity | December 18, 2014 at 07:44 AM
The linguist John McWhorter wrote an NYT opinion piece entitled Why Save a Language? where he argues why we should care about saving dying languages, basically...Lance Fortnow From Computational Complexity | December 11, 2014 at 08:22 AM
We've now completed five decades of favorite theorems.
1965-1974
1975-1984
1985-1994 (PDF)
1995-2004
And to recap the ten we chose this year from 2005-2014
...Lance Fortnow From Computational Complexity | December 4, 2014 at 08:23 AM
The Imitation Game starring Benedict Cumberbatch as Alan Turing opens in the US on November 28. If you read this blog you should see that movie. If one challenged...Lance Fortnow From Computational Complexity | November 20, 2014 at 08:25 AM
Inspired by the Dantzig Story I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving...Lance Fortnow From Computational Complexity | November 13, 2014 at 11:22 AM
We celebrate the 100th anniversary of the birth of George Dantzig today. In his obituary post we talked about his work on optimization, particularly the simplex...Lance Fortnow From Computational Complexity | November 8, 2014 at 08:34 AM
My long time blog readers should have no surprise on my final favorite theorem of 2005-2014.
Nonuniform ACC Circuit Lower Bounds by Ryan Williams (PDF)
We sawlist...Lance Fortnow From Computational Complexity | November 5, 2014 at 05:07 PM
Congratulations to the San Francisco Giants, winning the World Series last night. In honor of their victory let's talk metrics. Baseball has truly embraced metrics...Lance Fortnow From Computational Complexity | October 30, 2014 at 01:35 PM
On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what Mike has brought to research...Lance Fortnow From Computational Complexity | October 28, 2014 at 12:21 PM
The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft.
We feel that there should...Lance Fortnow From Computational Complexity | October 22, 2014 at 12:34 PM
NP (nondeterministic polynomial time) and NEXP (nondeterministic exponential time) are provably different classes by the nondeterministic time hierarchy. No surprise...Lance Fortnow From Computational Complexity | October 16, 2014 at 12:34 PM
Tis the season for the fall jobs post. Please list any jobs, academic or industrial, in theoretical computer science broadly construed in the comments to this post...Lance Fortnow From Computational Complexity | October 9, 2014 at 08:45 AM
In the past decade we have seen a strong program in algebraic circuit complexity. If you just define circuits using multiplication and addition gates, sometimes...Lance Fortnow From Computational Complexity | October 2, 2014 at 07:53 AM
I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser at MIT on Sunday, October 26 with a one...Lance Fortnow From Computational Complexity | September 27, 2014 at 09:38 AM
After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have...Lance Fortnow From Computational Complexity | September 24, 2014 at 04:36 PM
This week I'm back at Dagstuhl for the Workshop on Algebra in Complexity Theory. Bill is here as well and we hope to have a typecast for you later this week.
The...Lance Fortnow From Computational Complexity | September 22, 2014 at 01:51 PM