Computational Complexity

From Ryan O'Donnell Christie's is auctioning off a bunch of documents related to the history of computing. A '46 IAS repo...

This week I'm in the great Garden State of New Jersey (my home state) for back to back DIMACS workshops on Bounded Rationality and Ma...

Someone threw out this quote yesterday. Choosing your advisor is like choosing your spouse. I would say more like choosing your parent...

As you probably know today was the sixtieth anniverary of the liberation of Auschwitz . In religious school as a kid we read books, saw gr...

The list of accepted papers for STOC is up. Nice to see they accepted Trifonov's paper in addition to Reingold. Many other nice co...

A publisher sent me a copy of Blink a new book by Malcolm Gladwell. Gladwell wrote the very popular Tipping Point about phase transition...

Feel free to comment on last night's premier of Numb3rs , a show that has seemed to capture the interest of this community. For good r...

John Langford starts a new weblog Machine Learning & Theory . 2004 Year End Awards from Chris Masse's Predictions Market Dige...

A non-CS Chicago Alum asked me a question about free will and computation. I passed the question to David McAllester, an AI professor at T...

I have listed my favorite theorems for the first and second decades of my research career corresponding roughly to the third and fourth...

A few random comments as I read and write recommendation letters for various academic positions: Back in the old days, a candidate would...

Thanks to Rahul Santhanam for covering for me last week. If you are looking for a smart hard-working postdoc in complexity take a look a...

For Lance is back, and raring to go. It has been an interesting one week, but on the whole, research is probably easier than blogging, and c...

Lance has posted quite a lot on conference papers, review processes and the like recently, so one more won't hurt. Because of the resour...

Was leafing through some old copies of SIGACT News from the 80s. Once the forests of facial hair had ceased to distract me, I was intrigued ...

The theory of derandomization has had many successes, but challenges remain. Perhaps the most significant of these are finding a determinist...

We all like problems. But it's sort of sad that as our careers develop, we get to spend less and less time on problems that don't of...

Ex-guest blogger Adam Klivans is off to become the resident learning theorist at Austin. But no matter, Eli Ben-Sasson will be at TTI till t...

Hullo, all. Nice of Lance to lease me this space for a week, I most sincerely hope he won't come to regret it. I was thinking about...

I'm off the net next week. My student Rahul Santhanam will guest post in my absence. Enjoy!