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
STOC and More
The Snows of Maryland are keeping Bill away from this blog again. Here in Chicago we deal with snow (and even earthquakes) in stride--my kids still have yet toaccepted...
From Computational Complexity
Sam Roweis (1972-2010)
Sam Roweis, an NYU CS professor specializing in machine learning, took his own life last Tuesday night. Jennifer Linden and Maneesh Sahani set up a weblog to share...
From Computational Complexity
2009 Complexity Year in Review
We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits. Runners up include the Moser-Tardos...
From Computational Complexity
A Blog Sabbatical
With the end of the fall quarter I will take a break from the blog for a few months. This is not another End, just a chance to move my creative juices in another...
From Computational Complexity
Dequantification
After a talk on derandomization at Midwest Theory Day, someone asked if those techniques could also be used in quantum computing. In classical randomness under ...
From Computational Complexity
Complexity Vidcast 3
Quick announcement: If you are a student who wants to go to SODA but doesn't have the funds, click here. I had forgotten we did this. Here's a video of my daughter...
From Computational Complexity
The Probability of P=NP
Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P?NP (if it's independent it's still equal or unequal in...
From Computational Complexity
Who Pays for Trips?
If Professor Alice at Faber College visits Dr. Bob at the University of Southern North Dakota, who should cover Alice's expenses? It depends on who does the asking...
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