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
Cell Phones versus Drunk Driving
Most of you are familiar with the research that using a cell phone is just as dangerous as driving drunk. Method: We used a high-?delity driving simulator toResults...
From Computational Complexity
Is Computer Science Cool Again?
Back in 2005 I worried about loss of excitement about computer science among America's youth. Today computers have become almost as commonplace as televisionsFCRC...
From Computational Complexity
FCRC Early Registration May 16
One final reminder for the FCRC Conference. Early registration deadline is this Monday, May 16. There are a number of events at FCRC of interest to our readers...
From Computational Complexity
Those Happy Samoans
Below is a post I wrote in 2009 but for some reason never made it to this blog. But I had better post it now because, as I found out via Tony Wirth, Samoa is moving...
From Computational Complexity
Forty Years of P v NP
In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP...
From Computational Complexity
Don't Blame the Tech
Short Announcements: STOC Poster Submission Deadline is Monday. Jaime Morgenstern set up a google groups page for students to find roommates for STOC, FCRC andTechnology...
From Computational Complexity
Ravi Kannan wins the Knuth Prize
Ravi Kannan will receive the 2011 Knuth Prize for his algorithmic work, including approximating volumes of high-dimensional convex objects, computing the Frobenius...
From Computational Complexity
Choosing an Undergrad School
It is the time of year in the US that high school students have found out what schools have accepted them and now have to decide where to spend the next four years...
From Computational Complexity
Do You Know the Way to San Jose?
Lots of CS Goodness going on at FCRC June 4-11. New for 2011 the STOC Poster Session: Share your exciting research on theory's greatest stage! Submission deadline...
From Computational Complexity
Kanellakis and Grace Murray Hopper Prizes
The ACM announced several award winners today. Two of particular interest to the theory community. Craig Gentry, recipient of the Grace Murray Hopper Award for...
From Computational Complexity
A New Proof of the Nondeterministic Time Hierarchy
A nondeterministic time hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer. Z
From Computational Complexity
The Complexity of the Soul
A CS vision professor once told me "Of course we know there is an efficient algorithm for that humans can do it." Are we just nothing more than Turing machines...
From Computational Complexity
How I'm Spending my Spring Break
This week I returned to Dagstuhl for the workshop on Computational Complexity of Discrete Problems. I come here so often that when I tweeted that I was om way Dagstuhl...
From Computational Complexity
Computer Science Takes Over
We live in our own research areas. I focus on computational complexity and marvel at what our field has accomplished over my over 25 years in the field as wellseries...
From Computational Complexity
STOC 1989
A student at Northwestern gave a presentation about a STOC 1989 paper. I've been to well over a hundred conferences and the memories of many just merge into each...
From Computational Complexity
Les Valiant wins the Turing Award
In a definite case of when not if, Leslie Valiant will receive the 2010 ACM Turing Award, the highest honor in all of computer science. Valiant has done incredible...
From Computational Complexity
Greetings from Porto
Today we just finished the thesis defense of Andre Souto at University of Porto. Good News: He passed the defense so now we call him Dr. Souto. Better news: By...
From Computational Complexity
What I Tweeted
Various thoughts not restricted to 140 characters. Congrats to Mihalis Yannakakis for his election into the National Academy of Engineering as well as new Sloan...
From Computational Complexity