Computational Complexity

The accepted papers of STOC have been posted. A few on the list I have mentioned before including Daskalakis, Goldberg and Papadimitriou o...

A graduate student asks Is it better to have a large number of good papers or a small number of great papers? The answer is both, great pa...

First thanks to Bill Gasarch for his interesting takes on academic life. Another person who should have his own blog. I missed SODA again ...

GUEST BLOGGER: Bill Gasarch This is my last day guest blogging, so I'll end where I began, THREE points on LUDDITES I) Janos S...

GUEST BLOGGER BILL GASARCH TOPIC: How much is what we do influenced by non-scientific criteria? (BEFORE I START TODAYS BLOG- A REQUEST...

GUEST BLOGGER: Bill Gasarch (BEFORE I START TODAYS BLOG- A REQUEST.  EMAIL ME OTHER LUDDITE QUESTIONS- I WILL POST THE BEST ONES ON FRIDA...

Guest Blogger: Bill Gasarch HW AND EXAMS: While making up the lecture notes problems may arise naturally. Such as ``OH, I don't...

GUEST BLOGGER: Bill Gasarch (I will be guest blogging this week while Lance is on Vacation.) Are you a Luddite? The original Luddites wer...

I am on vacation next week and I've lined up Bill Gasarch as a guest Blogger in my absence. But today we have a guest post from Kamal Ja...

From Sanjeev Arora Bill Steiger of Rutgers is the new NSF program officer in charge of Theoretical Computer Science (TCS) and he has assum...

I have written up my ten favorite theorems for the decades 1985-1994 , 1995-2004 and 1965-1974 . This year we tackle the remaining decade ...

We watched the Chicago Bears Football team lose to Carolina with some friends who were extremely pessimistic the entire game, even though t...

In the third Complexitycast we talk about the Dutch Defense with new Ph.D. Troy Lee and several of the participants in his ceremony. MP3 (...

Every year I seem to write more letters, letters for those applying to graduate schools, letters for those looking for their first postdoc o...

My first trip to Amsterdam came during a whirlwind European tour in the summer of 1984 during my undergrad years. My second trip was for the...

This week I am making my nearly yearly visit to CWI in Amsterdam, where I spent a sabbatical year in the 90's. I will sit on the oppos...

Finding the 5th moon of Jupiter was a big deal. Finding the 14th moon was a big deal. But it's hard to get excited about the 63rd moon. ...

We need to rewrite the traffic laws in this country because they don't handle flying cars. We don't have flying cars, you say. We mi...

The Internet has led to a complete shifts in how we deal with storing and sharing information, but when it comes to academic papers the chan...

Edited from an email by Jan van Leeuwen and Jiri Wiedermann The year 2006 will be a special year for the foundations of logic and theoreti...