Computational Complexity

Its the time of year when Seniors who want to go to Graduate School should be pondering WHERE to go. There are other issues which I will add...

(Guest Post by Alexander Shen. Thanks to Lance for Suggesting it.) Andrej (Andrey) Muchnik died unexpectly last March, but the news didn...

As most people know the Amish avoid using certain technologies. They think that some technologies are disruptive to the community. In th...

There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned  the kruskal count . This is a card trick invent...

In my graduate complexity class I proved For all computable T there exists a decidable set A such that A &notin DTIME(T(n)). I then ...

I recently got an email that said roughly the following: Hi Bill, I am a grad student in combinatorial optimization, and I have a quest...

Request: If you want me to post a CALL FOR PAPERS or LIST OF ACCEPTED PAPERS or whatnot for a theory conference or some other conference, pl...

I was curious if my monograph Bounded Queries in Recursion Theory was still available so I went to amazon.com and typed in `William Gasarch...

I have been told quite often that You don't have to understand Quantum Mechanics to work in Quantum Computing. Thats a good thing s...

How does a theorem get to be believed to be true? There was a paper on this in 1979, Social Processes and Proofs of Theorems and Programs...

(Guest Blog by Jonathan Katz on the Koblitz Controversy) Like many others , I was very upset by a recent article by Neal Koblitz that...

(Guest post by Mihai Patrascu) A while ago, I promised the community around the International Olympiad in Informatics that I would brin...

When you are asked to referee a paper, should you accept the job? That is not todays topic. Today's posting is a rant! I got a req...

(Guest Blog by Amir Michail) As you may know, the Facebook platform was launched recently amid great excitement. This API allows developer...

Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry and Scott's entry on checkers, and the comments on it. the comm...

(Guest Informational Post by Phil Klein) Registration has opened for FOCS 2007, which will take place in Providence on October 20-23.  P...

Guest Post by Lance Fortnow As an anonymous commentor mentioned on Monday, I am moving to Northwestern University EECS in January. Northwe...

I will be teaching a Basic Graduate Course in Complexity Theory in the fall. Complexity Theory has too many theorems that you absolutely m...

There is a recent story and a request for a petition signing that SEEMS like we should support it, but rather than repeat the story, here ar...

Aravind Srinivasan: I have a great idea for a Blog Post! Bill Gasarch: What is it! Aravind Srinivasan: We all know where Scott A...