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...
I wake up bleary-eyed and jet-lagged at 6 AM begging of myself WHY? Why do I subject my body to such torturous trans-atlantic flight for three days of, of...
Nicole Immorlica continues to blog from FOCS. Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog...
The first day of FOCS is over. The highlight of the afternoon was the talk by Nancy Lynch, winner of the Knuth Prize. She began with, as one attendee put it, a...
(Even More from Nicole Immorlica, guest-posting from FOCS. This post is from Oct 22, 7:00PM) \br \br I remember taking writing classes in high school. We had a...
Another great guest post from Nicole Nicole Immorlica, from FOCS (Note from Bill G: This is one of several posts Nicole will be making from the Business...
(Another Guest post from Nicole!) The business meeting was fun thanks to Mihai! Click here to see why. Local arrangements: First, let me say how wonderful the...
(Another Guest post from Nicole!) More from the Business Meeting Funding status report: I'm not really the right person to blog about funding since I have...
Nicole's final FOCS post. And it's over! The 48th FOCS ended at 6.10pm with a talk on "The Computational Hardness of Estimating Edit Distance". About 50 brave ...
Recall that the Wolfram Prize which I blogged about here, was given to anyone who can determine if a certain Turing Machine was universal. It is now known that...
I want to extend a warm thanks to Nicole Immorlica for Guest blogging from FOCS. So I will: THANK YOU NICOLE! (Would have done this yesterday but if I had...
STOC deadline is coming up and the organizers have asked me to publicize a particular aspect of it. Note that in the call for papers it says: Papers that...
When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story: A 3-free set is a set with no...
Is the following TRUE or FALSE? For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are...
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.
