Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
From Computational Complexity
Erdős and Turing
Only nine months separate the births of two very influential mathematicians, Paul Erdős and Alan Turing, whose centenaries we celebrate this year and last. That's...
From Computational Complexity
2012 Complexity Year in Review
As we turn our thoughts from Turing to Erdős, a look back at the complexity year that was. Written with help from co-blogger Bill Gasarch. The complexity result...
From Computational Complexity
Flash Fill
Sometimes it just takes a simple new feature in a popular piece of software to remind us how computer science just does cool stuff. Excel 2013 has a new feature...
From Computational Complexity
The Fiscal Cliff
Unless the republicans and democrats get a deal before year's end, the country will head over the so-called "Fiscal Cliff" including a budget sequestration that...
From Computational Complexity
Too Much Competition?
On Friday the New York Times ran an article on how online retailers constantly adjust prices to match their competitors. Their ability builds on many tools from...
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...
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...
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...
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...
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...
From Computational Complexity
Sandy Extension
The deadline for submissions to STOC has been extended to Monday, Nov 5 2012 5:00 p.m. EST.
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...
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...
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...
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...
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...
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...
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 ...
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...
From Computational Complexity