Computational Complexity

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, ...

A girl told her father that history was much easier when he was in school. "Why?" he asked. She responded "Because there was ...

Last (but surely not least) day at FOCS 09! Jan Vondrak talked about some nice results that unify previous query complexity approaches in p...

After an early morning injection of much needed caffeine, Team Northwestern was ready for the next round of talks.  Today's program cons...

Michele and Michael continue their guest posts from Atlanta. The first day of FOCS is officially over. 8 sessions, 26 talks and 270 proceedi...

Alas, I'm not in Atlanta but in New York City for another meeting. Something different this time-- FOCS  through the eyes of two Northwe...

A few notes on Dagshul which Lance and I were at last week. I could tell you about the talks, but the website does a better job: here I...

(Guest Post by Dave Doty pointing to a blog by ***SORELLE*** which points to a roomate finding service for conferences.) Sorelle has ann...

[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...

Yesterday I posted a list of books that I want reviews of as SIGACT NEWS Book Review Column Editor. This resulted in an unintentional study ...

I have been the SIGACT NEWS Book Review Column Editor for a while now. Every issue I have a list of books that I WANT reviewed. This works p...

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 o...

In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold ...

Lance:  Because we don't have a good microphone, Bill and I decided to have our first typecast. Hi Bill. B ill: Hi Lance. We'll be t...

The talks Monday were after my own heart. The day started with relativization: The always entertaining Scott Aaronson talked on his approac...

This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity . I'll try to cover some of the ta...

Bill and I battle it out over what should be taught in a complexity course in our new vidcast .

On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences  motivated by my CACM article ...

The book Prime Obsessions has the following on Page 159: You will see it written that Hadamard was the last of the universal mathematicia...

When you get an invitation via email should you accept? How well targeted is it? Some real examples that I got. EXAMPLE ONE: I would...