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
Birthday Paradox Variance
First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US. Here's an interesting approach to the birthday paradox...
From Computational Complexity
DIMACS at 20
Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event. DIMACS has served the theoretical computer science community well over these two...
From Computational Complexity
Citing Papers
A student asked me which version of a research paper to cite, a journal (the last reviewed version) or a conference (the first reviewed version) of a paper. I generally...
From Computational Complexity
FOCS Videos
As I tweeted yesterday, the videos of talks from the 2009 FOCS conference are now online. Thanks to FOCS PC chair Daniel Spielman and Georgia Tech's ARC Centercollected...
From Computational Complexity
A Prayer Book for the Internet Generation
As a young kid in the Reform Jewish community we used the Union Prayer Book, a traditional book with Hebrew on the right and English on the left with lots of instructions...
From Computational Complexity
Jobs
As many university's still feel the effect of the financial crises, many have limited or no positions to hire new tenure-track faculty so I expect the academicUniversity...
From Computational Complexity
Breaking Walls
Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in November of 1989 that changed...
From Computational Complexity
Button Button
Here is the offer: If you press the button you will receive $200,000. The caveat: Someone you don't know will die. I was born during run of the original Twilight...
From Computational Complexity
Innovation
The new Innovations in Computer Science conference announced their accepted papers earlier this week including my paper with Rahul Santhanam "Bounding Rationality...
From Computational Complexity
Amir Pnueli (1941-2009)
Amir Pnueli, an expert in temporal logic and program verification who won the 1996 Turing Award, passed away Monday from a brain hemorrhage. His colleague Lenore...
From Computational Complexity
FOCS News
Last month I suggested that students should go to FOCS even if they didn't have a paper there. I doubt my post had much to do with it, but I heard FOCS did attract...
From Computational Complexity
Proud to be a Monomath
A girl told her father that history was much easier when he was in school. "Why?" he asked. She responded "Because there was so much less of it." An old joke, but...
From Computational Complexity
FOCS Last Day
Last (but surely not least) day at FOCS 09!Jan Vondrak talked about some nice results that unify previous query complexity approaches in proving lower bounds for...
From Computational Complexity
FOCS Day 2
After an early morning injection of much needed caffeine, Team Northwestern was ready for the next round of talks. Today's program consisted of talks more related...
From Computational Complexity
FOCS Day 1
Michele and Michael continue their guest posts from Atlanta.The first day of FOCS is officially over. 8 sessions, 26 talks and 270 proceedings pages have already...
From Computational Complexity
FOCS Day 0
Alas, I'm not in Atlanta but in New York City for another meeting. Something different this time--FOCS through the eyes of two Northwestern students, Michele Budinich and...
From Computational Complexity
The Humbling Power of P v NP
[Note from Bill: He now has an on-line list of papers who still need reviewers] Noam Nisan, back in grad school in the 80's made the following suggestion...
From Computational Complexity
Typecasting Again
Lance: Welcome to our second typecast on the last full day of Dagstuhl. I may not see Bill for a while so we'd thought we'd get in one more chat before we go our...
From Computational Complexity
Thanks for the Fuzzy Memories
In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their...
From Computational Complexity