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
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
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....
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...
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...
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...
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...
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...
From Computational Complexity
Ten Years of the Complexity Blog
On August 22, 2002 I wrote the following immortal words to start this blog This is my complexity web log. I'll be giving random thoughts about computational complexity...
From Computational Complexity
Is the Turing Test Still Interesting?
Besides the Turing machine, Alan Turing also developed what we now call the Turing Test in Turing's seminal 1950 AI paper "Computational Machinery and Intelligenc...
From Computational Complexity