I have been to New Orleans twice. First for the 1991 STOC conference which overlapped the Jazz and Heritage festival. Then again in 1994, one last fling when...
Bill Gasarch wants your help to judge a new book. I am reviewing Encyclopedia of Cryptography and Security for a future SIGACT NEWS book review column. I will...
As theoretical computer science grew during the past twenty years, the general theory conferences STOC and FOCS could no longer present all of the good papers...
From Anupam Gupta A favor: the FOCS conference registration site is open; could you put up a small post on your blogs letting people know this, along with the...
A student asked me why P/poly was an interesting class? A very interesting class with a funny name. It combines time and program-size complexity, and...
John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki . For those not up on the nomenclature, a wiki is a specially designed web...
If you only read these posts, say through the mailing list or a newsreader, then you miss the best writing on this weblogthe comments. Take some time (and it...
August Edition In the 1950's Friedberg and Muchnik independently showed there existed computably enumerable but non-computable sets that are strictly weaker ...
Jonathan and Me My brother is out in California co-producing a movie Certifiably Jonathan , a quasi-documentary about Jonathan Winters. The basic story:...
A comment to Tuesday's post mentions the result If Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses. He gives credit to Schning...
The movie Proof opens today after more than two years after a number of the scenes were filmed at the University of Chicago, some right in Ryerson (home to...
The STACS conference has ruined my weekend. How? They extended their submission deadline from Friday to today. You might say why don't I just pretend the...
Congratulations to Jon Kleinberg, theory's newest genius . Suresh reports that Tobias Gerken has shown that given any large enough set of points in the plane...
I've often heard that scientists have unusually big egos. I don't disagree, egos are a part of being a scientist, a great motivator for us. I still love that...
An anonymous guest post. I was at a conference this summer where I saw several talks about distributed optimization that used the terms "social optimum" and ...
Speaking of names, the associated press released a story yesterday More Colleges Offering Game Theory Courses about new courses on creating video games. CNN...
The last week of the major league baseball regular season starts tonight with some tight races ahead . The wild card adds some interesting complexity to the...
In 1983, Michael Sipser suggested an approach to separating P and NP. One way to gain insight into polynomial time would be to study the expressive power of...
I once met a professor at Chicago that would say "My business is war, and business is good." I have a food scientist friend from college who did his doctorate...
The Nobel Prizes will be announced this week and I predict that no one will win the Nobel Prize in computer science for the 105th consecutive year. Computer...
We had a high pitch tone coming from somewhere in our family room but we couldn't find the source. I shut down the power in case the sound was coming from the...
In the second biggest sports story in Chicago (after the White Sox rout of Boston), the Chicago Bulls basketball team traded Eddy Curry to the New York Knicks...
A conversation with a graduate student today. Student: Why doesn't FOCS have a best paper award this year? Me: They often don't announce the winners until the...
My first computer was a TRS-80, my second an Apple IIe. In college I mostly programmed in IBM 370 assembly code. But in graduate school (first at Berkeley and...
A colleague is refereeing a paper in a non-computer science area that shows a certain computational problem is NP-complete. The proof uses a simple reduction...
Piotr Indyk, himself a 2003 Packard Fellow, writes On the recent blog topic of awards : you might be interested to know that Venkat Guruswami just received a...
September Edition Usually we think of the class NP as either languages accepted in polynomial-time by a nondeterministic Turing machine or languages with ...
As you can see from the timestamp of this post, I came into work quite early this morning. I had to drive and needed an early start (about 6 AM) to beat ...
Fonts are the last thing I want to worry about when I write a research paper. Unfortunately fonts have often become the last thing I need to worry about when I...
The University of Chicago denying tenure to an assistant professor is rarely a breaking news story. Yet political scientist Daniel Drezner's case received...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
