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
A Breakthrough Circuit Lower Bound
On October 8th, when in my graduate complexity course as we discussed the 1987 Razborov-Smolensky result that one can't compute the Modp by constant-depth polynomial...
From Computational Complexity
The FOCS Experience
You can now watch videos of the recent FOCS talks online. Glencora, who I had the pleasure of meeting at the conference, has her favorites. If you watch any, check...
From Computational Complexity
By Any Other Name Would Be Just As Hard
In 1973 Donald Knuth searched for a name for the hardest problems in NP. Steve Cook didn't give a name in his paper and Karp called them P-complete. Knuth suggested...
From Computational Complexity
FOCS Part II
I'm heading back to Chicago this morning. Dan Spielman had a special talk in honor of his recent Nevanlinna prize. He gave an amazing talk (as always) about solving...
From Computational Complexity
FOCS Part I
Some thoughts from the FOCS conference in Las Vegas. One result I hadn't seen before I heard people excited by, Determinant Sums for Undirected Hamiltonicity by Andreas...
From Computational Complexity
A Note from the Trenches (Guest Post from Michael Mitzenmacher)
Former blogger Michael Mitzenmacher talks about being chair and not blogging. In a day for guest posts, over at Geomblog, David Johnson wants to know practical ...
From Computational Complexity
My Trip to Denmark
Last week I had a pleasant short trip to Aarhus, Denmark for the inauguration of the new Center for Research in the Foundations of Electronic Markets. Kevin Leyton...
From Computational Complexity
Beno
Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line.
From Computational Complexity
The NSF Takes Shape
As I've mentioned before, the NSF is turning over top to bottom especially in computer science. Most of the pieces are now in place so let's check out the new personnel...
From Computational Complexity
Partha Niyogi (1967-2010)
University of Chicago Computer Science and Statistics Professor Partha Niyogi passed away on Friday after a battle with brain cancer. Partha worked in machine...
From Computational Complexity
The Annual Fall Jobs Post
The CRA is working on setting guidelines for job deadlines to help out with some of the gridlock in the job market. Many of the top departments have already moved...
From Computational Complexity
NRC Rankings
The NRC "rankings" of Graduate programs was released yesterday. I put up a Google spreadsheet of the CS rankings. Phds.org will also generate rankings using various...
From Computational Complexity
The Theory Social Network
Derrick Stolee tweeted that the videos from the 2010 Complexity Conference are now on-line. If you want to attend a conference live, don't forget early hotel and...
From Computational Complexity
The World in Its Own Terms
The New York Times Magazine last Sunday focused on technology on education. Lots of good reads but what caught my eye was an article by Microsoft Research's Jaron...
From Computational Complexity
How Can You Spend $150 Million?
Suppose you happen to have $150 million burning in your pocket that you want to use to help the theoretical computer science community ($150 million endowed will...
From Computational Complexity
FOCS Travel Support (Guest Post by Paul Beame)
The program for the FOCS 2010 has an excellent set of selected papers and in addition has tutorials on Saturday by Ketan Mulmuley, Mihai Patrascu, and Tim Roughgarden...
From Computational Complexity
How to Write Up Major Results
First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP, deadline...
From Computational Complexity
CS Happenings
Yesterday I was at a meeting of the CCC Council, add in a couple of emails and I have lots of short notes on CS stuff. In these meetings I get to hear about CS...
From Computational Complexity
New Institute for Theory of Computing
The Simons Foundation has announced a competition to establish a new Institute for the Theory of Computing in the United States. Computation (and its abstractTTI...
From Computational Complexity