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...
On my last blog I asked the following: TRUE OR FALSE: For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same...
(Guest post by Kamal Jain Resubmitting the rejected papers from FOCS to STOC? If your paper was rejected by FOCS and you're submitting it to STOC, here are my...
Richard Beigel is now one of five Program Director at NSF for CISE/CCS/TF (TF= Theoretical Foundations) This is the job previously held by William Steiger (who...
Computational Complexity Conference 2008 (CCC 2008) submissions website is now open: go here for submissions website or go here for more info on the conference...
Often I see something in real life that inspires a math problem. Could be a math problem for an exam or a student project or (more rarely) serious research....
Recall the tables problem, which I now state more clearly than I did in my last post: n couples go to a resturant. They will sit at a rectangular table that...
How to get an NSF grant? If I knew I would have more Grant money. However, I was emailed the following powerpoint slides with the request to post them on my...
What did I do over Thanksgiving? I read Ernie Croots's excellent exposition of Szemeredi's Regularity Lemma which is here It is sometimes easier to learn stuff...
I recently got the following email. I sent to papers to a conference TMFCS08 (Theoretical and Mathematical Foundations of Computer Science) and got accepted,...
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.
