The job market for theorists is rough, and for logicians even rougher. Hence some seek employment outside of academia, outside of research labs, outside of...
This is the 1000th posting on the complexity blogs. 958 were when Lance was running it and the rest (I'll let you do the math) were when I was running it. This...
&pi, the ratio of the circumference to the diameter of a circle, is one of the most important constants in Math. However, &pi could just as easily have been...
Aravind Srinivasan: I have a great idea for a Blog Post! Bill Gasarch: What is it! Aravind Srinivasan: We all know where Scott Aaronson ended up- MIT, but ...
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 are pointers. It...
I will be teaching a Basic Graduate Course in Complexity Theory in the fall. Complexity Theory has too many theorems that you absolutely must cover. Hence you...
Guest Post by Lance Fortnow As an anonymous commentor mentioned on Monday, I am moving to Northwestern University EECS in January. Northwestern also hired...
Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry and Scott's entry on checkers, and the comments on it. the comments on it. Then Aaron...
(Guest Blog by Amir Michail) As you may know, the Facebook platform was launched recently amid great excitement. This API allows developers to integrate their...
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 request to referee a paper that...
A while ago, I promised the community around the International Olympiad in Informatics that I would bring them into the conscience of the theory community, and...
(Guest Blog by Jonathan Katz on the Koblitz Controversy) Like many others, I was very upset by a recent article by Neal Koblitz that appears in the Notices of...
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 by DeMillo, Lipton,...
I have been told quite often that You don't have to understand Quantum Mechanics to work in Quantum Computing. Thats a good thing since I've also been told...
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'. It had 40 hits....
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, please email me and I...
I recently got an email that said roughly the following: Hi Bill, I am a grad student in combinatorial optimization, and I have a question that I was hoping...
In my graduate complexity class I proved For all computable T there exists a decidable set A such that A ¬in DTIME(T(n)). I then had on the homework For all...
There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned the the Kruskal Count (See also this link) This is a card trick...
As most people know the Amish avoid using certain technologies. They think that some technologies are disruptive to the community. In the past the Bishops...
(Guest Post by Alexander Shen. Thanks to Lance for Suggesting it.) Andrej (Andrey) Muchnik died unexpectly last March, but the news didn't spread out, so I am...
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 address in later...
I caught an episode of DEAL-NO DEAL recently (see this for a description). The math behind this game has been described in blog postings of Lance (see this as...
Pretend you didn't know the Karp-Lipton theorem. Consider the following two statements SAT has poly size circuits. The Poly Hierarchy collapses. You probably...
Richard Stallman gave a talk at University of Maryland at College Park. He is the head of the free software foundation. The terminology `free software' does...
Is Mathematics a Science? Is Computer Science a Science (hmmm- it has to be, its in the name :-) )? Is Richard Stallman a computer scientist? How about Bill...
In Russia a notorious spammer was assassinated Is this a crime? Should it be? Consider the contrast: - Killing one person. How many people suffer and how much?...
I wish to start a more intelligent discussion of spam then my last post lead to (my fault). And YES, the story I pointed to was a hoax. Is Spam a big problem?...
I find the following result to be really interesting but can't quite say why: (For this exposition &lem means poly-m-reduction) Let SAT17 be the set of...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
