We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a...
Chris Leonard who edits the Elsevier journals in theoretical computer science has started a weblog Computing Chris . He plans to address some of the concerns...
When I was in grade school we learned that Jupiter had twelve moons. We had a test. "How many moons does Jupiter have?" I wrote "12" and it was marked correct....
An email from Rocco Servedio. Did you see this New York Times article ? Thought you might be interested in pointing this out on the weblog, maybe a CS theory...
I am just finishing the last of three west coast trips this summer. I went to the Complexity conference, two universities (U. Wash and Caltech), three...
July Edition As a graduate student, Manuel Blum wanted to study computational complexity freed from any specific machine model. His paper set the tone for much...
Sanjeev Arora and Bernard Chazelle write the Viewpoint Column Is the Thrill Gone? in this months Communications of the ACM . One wonders if the failure of...
Robin Houston writes Although I'm not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the...
Elsevier is opening up I&C for the rest of the year. The Publisher and Editorial Board of Information and Computation are pleased to announce that for one...
Let's look at some relativized worlds which really push the limits of what we don't know how to prove. Once again I refer you to the zoo for definitions of...
The US has reached its limit for H1-B visas not just for this fiscal year but for the next. A foreign technical worker wanting to work in the US wouldn't be...
Simulated Annealing is a heuristic technique for optimization problems. Think of an optimization problem as hills and valleys where you want to find the lowest...
In a popular summer movie Wedding Crashers , two friends go to weddings and receptions uninvited for food, drink, entertainment and to pick up single women. We...
I am back from our family vacation to the Black Hills of South Dakota. Thanks to Ryan O'Donnell for guest blogging. I have donated $26 to hurricane relief in...
Ronald Fagin writes in response to my post The New Research Labs . Lance has invited us to give an update on the state of theory at the IBM Almaden Research...
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 ...
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.
