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
The Theory Postdoc Culture
FOCS Call for Papers posted. Deadline April 13. The CRA organized a committee that put together on a white paper on whether postdocs are healthy for Computer Science...
From Computational Complexity
The Ideal Conference
I found the perfect CS conference. A meeting where computer scientists from all its subdisciplines come together. Not with the purpose of presenting their current...
From Computational Complexity
Why My Kids Trust Wikipedia
Guest post from Annie and Molly Fortnow Our teachers used to tell us not to use Wikipedia because anybody can edit it and therefore it isn't trustworthy. A couple...
From Computational Complexity
Coloring Maps
The four color theorem means you can color the United States in four colors. But can you color it in three? Try it before you read on. The answer is no. Consider...
From Computational Complexity
The Enduring Legacy of the Turing Machine
Last Februrary Peter Wegner asked if I would be interested in writing an article for a series in ACM Ubiquity on "What is Computation?" Our expanding collaboration...
From Computational Complexity
Complexity Year in Review 2010
Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC0, just one of many exciting papers this year. The runner up is...
From Computational Complexity
America's Most Important Algorithm
Yesterday the Census Bureau announced the new apportionment of the 435 representatives to states based on the 2010 census. Illinois lost one representative. Texas...
From Computational Complexity
Do Uniform Lower Bounds Matter?
From Ryan Willams' paper: Non-uniform lower bounds establish impossibility results for computation in the physical world: it could be that P ? NP, yet NP-complete...
From Computational Complexity
Complexity as Friction
What advantages can we get from computational hardness? Cryptography and pseudo-random number generators come to mind. But perhaps the universe made computation...
From Computational Complexity
Game Theory, Terrorism, Hardness and SAT Solving
Last week I attended the Army Research Office sponsored Workshop on Reasoning in Adversarial and Noncooperative Environments related to Topic #22 of the 2011MURI...
From Computational Complexity
Is Ryan's Theorem Only Interesting to Complexity Theorists?
Last week, the complexity theory bloggers Dick, Scott, Luca and myself all heaped praise on Ryan Williams' new circuit lower bound, NEXP not in ACC0. Outside the...
From Computational Complexity
Dr. Scott Goes to Washington
Fellow blogger Scott Aaronson was chosen as one of 19 NSF PECASE awardees and wins a trip to the White House. Congrats to Scott! He received the award "for pushing...
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