Computational Complexity

On Thursday Aug 26 Lance stated Bill is at Barriers II in Princeton and promises a full report upon his return. Not quite sure I promised ...

The Simons Foundation has announced a competition to establish a new Institute for the Theory of Computing in the United States. Computat...

I got the following request from a reader. I have a question about TCS journals. As I am trying to follow your advice on being more dilige...

Bill is at Barriers II in Princeton and promises a full report upon his return. Ask many computer scientists what happens if P = NP and y...

Three annoucements (the last two I was asked to post) ANNOUCEMENT 1: Congrads to fellow blogger ***SORELLE*** who got her PhD recently. I...

The Aug 19, 2010 episode of Futurama had NEW math in it! It also has some other math refs. This website claims that Ken Keeler, one of ...

(Guest Post by Ben Fulton.) "At first glance, scheduling does not seem like a topic that requires much attention from computer scie...

Bill and I are strong believers in freedom of speech and have long since had an open comment policy, allowing anonymous comments, no moderat...

Many changes at the National Science Foundation both in programs and personnel. Some highlights of upcoming  CISE programs . Expeditions  ...

Dan Spielman wins the Nevanlinna prize for "smoothed analysis of Linear Programming, algorithms for graph-based codes and applications...

The following conversation is a fictional version of a real conversation. Lance: Bill, Wed August 18, 2010 is Paul Turan's 100th bi...

(This is likely my last post on the alleged P NE NP paper unless more real news on it occurs. The only real news I can see happening at this...

This summer I took a two part vacation: Touring Ireland July 26-August 5, with my wife to celebrate twenty years of marriage and a short tri...

(Update on P vs NP: The proof uses Finite Model Theory which is sometimes called That stuff that Neil Immerman does. . Neil Immerman has fou...

(Update on alleged P NE NP proof: There are some issues with it. See these posts on Lipton's blog: here and here and also see a Wikip...

Let me be he last on the block to tell you that an alleged proof of P ≠ NP is out there. NOT posting on it would be absurd; however, I canno...

RECALL from my last post the following game: Let f(n) be a non-decreasing function from naturals to naturals. Consider the following ga...

Let f(n) be a monotone increasing function from N to N. (CLARIFICATION ADDED LATER: N is the naturals., f is non-decreasing) Consider the fo...

The following problem is from Doctor Eco's Cyberpuzzles . I have shortened and generalized it. We are going to put numbers into boxes....

I recently a letter from WETA (public TV) which I quote from: This letter is quite different from any we've ever sent to you. For ye...