Blogroll | Communications of the ACM

From Computational Complexity

STOC Business Meeting

This week I'm at the Federated Computing Research Conference in Portland, a collection of many mostly ACM conferences. Last night was the STOC business meeting.... Lance Fortnow
From Computational Complexity | June 16, 2015 at 04:53 PM

From Computational Complexity

A Metric Group Product

A guest post by Dylan McKay, recently graduated from Georgia Tech and soon to be PhD student at Stanford. Here a cute puzzle motivated by a pair of undergrads... Lance Fortnow
From Computational Complexity | June 11, 2015 at 08:37 AM

From Computational Complexity

Award Season

László Babai will receive the 2015 Knuth Prize and Daniel Spielman and Shang-Hua Teng will receive the 2015 Gödel Prize. ACM issued a press release for both... Lance Fortnow
From Computational Complexity | June 1, 2015 at 04:46 PM

From Computational Complexity

John Nash (1928-2015)

John Nash and his wife Alicia died in a taxi accident, returning from the airport after he received the Abel prize in Norway. The public knew John Nash as the "Beautiful... Lance Fortnow
From Computational Complexity | May 25, 2015 at 10:56 AM

From Computational Complexity

Theory Jobs 2015

In the fall we list theory jobs, in the spring we see who got them. Like last year, I created a fully editable Google Spreadsheet to crowd source who is going where... Lance Fortnow
From Computational Complexity | May 18, 2015 at 08:24 PM

From Computational Complexity

Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity

Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by Hennie and Stearns. Photo courtesy... Lance Fortnow
From Computational Complexity | May 14, 2015 at 09:34 AM

From Computational Complexity

The Virtuous Cycle

Last week we have a celebration of the new CS graduates at Georgia Tech where each graduating student says what their plans are for next year. Other than the few... Lance Fortnow
From Computational Complexity | May 7, 2015 at 07:30 AM

From Computational Complexity

Is Logarithmic Space Closed Under Kleene Star?

A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked the oracle of all things... Lance Fortnow
From Computational Complexity | April 29, 2015 at 07:50 PM

From Computational Complexity

Fifty Years of Moore's Law

Gordon Moore formulated his famous law in a paper dated fifty years and five days ago. We all have seen how Moore's law has changed real-world computing, but how... Lance Fortnow
From Computational Complexity | April 24, 2015 at 07:20 AM

From Computational Complexity

PH Infinite Under a Random Oracle

Benjamin Rossman, Rocco Servedio and Li-Yang Tan show new circuit lower bounds that imply, among other things, that the polynomial-time hierarchy is infinite relative... Lance Fortnow
From Computational Complexity | April 16, 2015 at 09:14 AM

From Computational Complexity

Baseball is More Than Data

As baseball starts its second week, lets reflect a bit on how data analytics has changed the game. Not just the Moneyball phenomenon of ranking players but also... Lance Fortnow
From Computational Complexity | April 14, 2015 at 01:01 PM

From Computational Complexity

FCRC 2015

Every four years the Association for Computing Machinery organizes a Federated Computing Research Conference consisting of several co-located conferences and some... Lance Fortnow
From Computational Complexity | April 9, 2015 at 07:12 AM

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