Computational Complexity

A commenter a LOOOOONG time ago left the following: Tell me, Gasarch, how in the world do you get your papers published when you consisten...

(Another Guest post about ICS 2010. From Aaron Sterling. Is he on his way to break the MOST GUEST POSTS IN A YEAR record? I doubt it- I thin...

(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chanc...

One of the comments on this blog pointed out correctly that for a theorem to be accepted by the community is not a Eureka Moment. It is a s...

Two sites to look for jobs at: Lance Fortnow set up this blog that collects theory annoucments including jobs: here Boaz Barak Ob...

I warned Lance to wait until early Jan to post 2009 Complexity Year in Review . It was my fear that by posting it on Dec 28, 2009 he may mi...

The last few posts on ICS in China have lead to off-topic (though maybe they were not off topic) comments on whether we should have conferen...

(This is my last post until next week Tuesday.) Many people believe the following: FOCS and STOC only take technically hard results on...

(Guest Post by Rahul Santhanam) Title: ICS I : Snapshots 1. Local Arrangements: Kudos to the organizing committee for going far bey...

Innovations in Computer Science 2010 (post #2) Guest Post by Aaron Sterling This is the sequel to my previous post on ICS 2010, the...

Innovations in Computer Science 2010 (post #1) Guest post by Aaron Sterling This is the first of three posts about ICS 2010 , the m...

The COLT (Computational Learning Theory) call for papers is out. (Actually its been out since October but I was only recently emailed it.) ...

When I took my first graduate course in complexity theory the professor had FOUR books on the REQUIRED FOR THE COURSE list. I bought all fou...

Some misc thoughts on set theory inspired by yesterdays comments and other things. Geometry: Use Euclidean Geometry when appropriate, for...

One of the founders of Conservapedia (a conservative alternative to Wikipedia) said the following on The Colbert Report: There is an abso...

We go all the way back to January for the paper of the year, Mark Braverman's  Poly-logarithmic independence fools AC0 circuits . Runner...

(This is my last blog of the year. Lance will interrupt his blog sabbatical to do an END OF THE YEAR blog later.) The TV show MONK rece...

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to constru...

The following problem was problem 1 (the easy one) on the Maryland Math Competition 2009 (I will later report on how the students did on it...

(Tal Rabin requested to post this so I am doing so. This post is essentially her email, so call it a guest post.) There will be a Women ...