Blogroll | Communications of the ACM

From Computational Complexity

App Love

First a shout out to our friends up north on the 30th anniversary of the New York Theory Day this Friday. Just two years ago I wrote a post Gadget Love but now... Lance Fortnow
From Computational Complexity | November 28, 2012 at 11:12 PM

From Computational Complexity

Recursion Theorem follows from Church-Turing

During a homework assignment in a graduate complexity course I took at Cornell back in 1985 I used the following reasoning: Since a computer code sits in RAM that... Lance Fortnow
From Computational Complexity | November 20, 2012 at 09:19 PM

From Computational Complexity

A Simple PSPACE-Complete Problem

Back in the typecast last month I promised a simple PSPACE-complete game in a future post. Here it is: The SET GAME Given: A collection of finite sets S1,...,Sk... Lance Fortnow
From Computational Complexity | November 15, 2012 at 02:00 PM

From Computational Complexity

Fifty Years of Computational Complexity

From Juris Hartmanis’ Observations About the Development of Theoretical Computer Science on the research leading to his seminal 1965 paper On the Computational... Lance Fortnow
From Computational Complexity | November 11, 2012 at 01:41 PM

From Computational Complexity

Produce or Perish

Every year or so the National Science Foundation releases a new version of the holy bible of grant submission procedures, the Grant Proposal Guide. Last month's... Lance Fortnow
From Computational Complexity | November 5, 2012 at 01:51 PM

From Computational Complexity

Sandy Extension

The deadline for submissions to STOC has been extended to Monday, Nov 5 2012 5:00 p.m. EST. Lance Fortnow
From Computational Complexity | October 31, 2012 at 07:43 PM

From Computational Complexity

Fall Jobs Post

Time again for the annual fall jobs post. As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out the... Lance Fortnow
From Computational Complexity | October 29, 2012 at 04:50 PM

From Computational Complexity

Song of the Complexity Classes

I tweeted the audio of this song last week and here is the video. Recorded at Dagstuhl on October 18th. Written by Fred Green who also plays piano. Performed by... Lance Fortnow
From Computational Complexity | October 22, 2012 at 01:55 PM

From Computational Complexity

Short Announcements

With a shout out to the friendly folks attending FOCS this week, some short announcements. Read the STOC CFP before you submit the paper. There are significant... Lance Fortnow
From Computational Complexity | October 20, 2012 at 11:42 PM

From Computational Complexity

Dagstuhl Typecast

Nerd Shot from Dagstuhl Seminar 12421 Lance: Welcome to another Typecast from beautiful Schloss Dagstuhl. I’m here with Bill for the Workshop on Algebraic.Bill... Lance Fortnow
From Computational Complexity | October 17, 2012 at 07:49 PM

From Computational Complexity

Matching Nobel Prizes

This week Bill and I have traveled to Germany for the Dagstuhl Seminar on Algebraic and Combinatorial Methods in Computational Complexity. Plenty of newly minted... Lance Fortnow
From Computational Complexity | October 15, 2012 at 03:00 PM

From Computational Complexity

Why Does College Cost So Much?

When John Hennessey gave his talk on MOOCs at the CRA Snowbird meeting he recommended the book Why Does College Cost So Much? by Robert Archibald and David Feldman... Lance Fortnow
From Computational Complexity | October 11, 2012 at 11:39 AM

From Computational Complexity

Close to Genius

The MacArthur Foundation announced their 2012 Fellows, also know as the genius awards. Among the list two names of interest to my readers, Maria Chudnovsky and ... Lance Fortnow
From Computational Complexity | October 3, 2012 at 11:19 PM

From Computational Complexity

Things a Complexity Theorist Should Do At Least Once

A few weeks ago, Suresh wrote a post Things a TCSer should have done at least once with the caveat This list is necessarily algorithms-biased. I doubt you'll need... Lance Fortnow
From Computational Complexity | September 27, 2012 at 02:04 PM

From Computational Complexity

Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins.... Lance Fortnow
From Computational Complexity | September 20, 2012 at 01:20 PM

From Computational Complexity

Theory Conferences Galore

Early registration for the FOCS conference in New Jersey is September 27th. There is some travel support available for students and postdocs, deadline is this Friday... Lance Fortnow
From Computational Complexity | September 19, 2012 at 05:57 PM

From Computational Complexity

Max Flow

A couple of weeks ago Suresh tweeted the following result of James Orlin Max flows in O(nm) time or better. jorlin.scripts.mit.edu/Max_flows_in_O… — Suresh Venkat... Lance Fortnow
From Computational Complexity | September 13, 2012 at 05:37 PM

From Computational Complexity

The Time of Research

Among the many conference/journal discussions, one systems person said the reason they don't publish in journals is that their work is very dependent on current... Lance Fortnow
From Computational Complexity | September 6, 2012 at 02:01 PM

From Computational Complexity

The Net or the Jet

I spent the first half of my life in the jet age but not in the Internet age. I could fly anywhere in the world but the fastest way to get a research paper to another... Lance Fortnow
From Computational Complexity | August 30, 2012 at 12:10 PM

From Computational Complexity

Knuth Prize

Leonid Levin will receive the Knuth Prize, and give the corresponding lecture, at FOCS this year. The Knuth Prize is jointly given by ACM SIGACT and the IEEE TC... Lance Fortnow
From Computational Complexity | August 26, 2012 at 03:30 PM