Blogroll | Communications of the ACM

From Computational Complexity

Intuitive Proofs

As I mentioned a few months ago, I briefly joined an undergraduate research seminar my freshman year at Cornell. In that seminar I was asked if a two-dimensional... Lance Fortnow
From Computational Complexity | March 30, 2015 at 02:36 PM

From Computational Complexity

News Aplenty

Both the Turing Award and the Abel Prize were announced this morning. MIT databases researcher Michael Stonebraker wins the ACM Turing Award. He developed INGRES... Lance Fortnow
From Computational Complexity | March 25, 2015 at 02:10 PM

From Computational Complexity

Feeling Underappreciated

As academics we live and die by our research. While our proofs are either correct or not, the import of our work has a far more subjective feel. One can see where... Lance Fortnow
From Computational Complexity | March 19, 2015 at 09:58 AM

From Computational Complexity

Quotes with which I disagree

Often we hear pithy quotes by famous people but some just don't hold water. "Computer science is no more about computers than astronomy is about telescopes." Usually ... Lance Fortnow
From Computational Complexity | March 12, 2015 at 07:25 AM

From Computational Complexity

Leonard Nimoy (1931-2015)

Bill and I rarely write joint blog posts but with the loss of a great cultural icon we both had to have our say. Bill: Leonard Nimoy (Spock) died last weekLance... Lance Fortnow
From Computational Complexity | March 2, 2015 at 03:46 PM

From Computational Complexity

Selecting the Correct Oracle

After my post last week on the Complexity accepts, a friend of Shuichi Hirahara send Shuichi an email saying that I was interested in his paper. Shuichi contacted... Lance Fortnow
From Computational Complexity | February 26, 2015 at 05:22 PM

From Computational Complexity

Eliminate the Postal Service

It's gotten very difficult to mail a letter these days. There are no mailboxes along my ten mile commute. Georgia Tech has contracted with an outside company to... Lance Fortnow
From Computational Complexity | February 23, 2015 at 12:11 PM

From Computational Complexity

And the Winners Are...

I always like that the announcement of accepted papers for the Computational Complexity Conference happens around the time of the Academy Awards. These acceptances... Lance Fortnow
From Computational Complexity | February 19, 2015 at 07:06 AM

From Computational Complexity

Richard Hamming Centenary

Richard Hamming was born a hundred years ago today in Chicago. He worked on the Manhattan Project during World War II, moved to Bell Labs after the war and started... Lance Fortnow
From Computational Complexity | February 11, 2015 at 07:23 AM

From Computational Complexity

Computers Turn Good and Evil

Entertainment Weekly proclaimed 2015 the year that artificial intelligence will rule the (movie) world with talk of the Terminator reboot, the new Avengers movie... Lance Fortnow
From Computational Complexity | February 5, 2015 at 07:43 AM

From Computational Complexity

Reusing Data from Privacy

Vitaly Feldman gave a talk at Georgia Tech earlier this week on his recent paper Preserving Statistical Validity in Adaptive Data Analysis with Cynthia Dwork, Moritz... Lance Fortnow
From Computational Complexity | January 29, 2015 at 07:53 AM

From Computational Complexity

There Should be an Algorithm

My high school daughter Molly was reading her Kindle and said "You know how you can choose a word and the Kindle will give you a definition. There should be anword... Lance Fortnow
From Computational Complexity | January 22, 2015 at 08:03 AM

From Computational Complexity

The Impact Factor Disease

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

From Computational Complexity

The History of the History of the History of Computer Science

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

From Computational Complexity

2014 Complexity Year in Review

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

From Computational Complexity

Undergraduate Research

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

From Computational Complexity

The NIPS Experiment

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

From Computational Complexity

The Ethics of Saving Languages

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

From Computational Complexity

Favorite Theorems Recap

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

From Computational Complexity

A November to Remember

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