Computational Complexity

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...

Richard Lipton had a wonderful post asking for a seventh Millennium Prize now that Poincare's conjecture has been solved. I posted ...

Considerable discussion about funding at CRA Snowbird . Ken Gabriel, Deputy Director of DARPA, talked about how DARPA is restructuring its ...

I just returned home from my first trip to the  CRA Snowbird Conference , the biennial meeting of CS chairs and other leaders in the CS comm...

I will be sending my next book review column for SIGACT NEWS off on July 28, 2010. It has LOTS of books on its BOOKS I WANT REVIEWED list. Y...

The Job Market in Theory (likely in all of academia) has more randomness and arbitrariness (are those the same?) then people may realize. ...

What do you get out of this paragraph (from Charlie Stross'  The Atrocity Archives  via Daniel Lemire ) The [Turing] theorem is a hack...

(This post is similar to this old post . I am posting this anyway since when I first posted I made fundamental mistake. I fixed it the point...

Last week, the Center for Computational Intractability hosted a Geometric Complexity Theory Workshop . Geometric complexity theory (GCT) i...

Is it possible for someone to be denied Full Prof? Yes, but it is rare. Is it possible for someone to fail a PhD defense? Yes, but it is ...

a conflict-of-interest? Some thoughts. Thought One PROF: I can't vote on Professor X's Full Prof case since I have a confli...

At a CCC Council meeting last week, a common theme emerged. The Army is "swimming with sensors and drowning in data". Biologists ...

FOCS accepts , abstracts  and  PDFs . The conference itself will be held October 23-26 in Las Vegas. There is a proposed TCS version of ...

Consider the following problem: A hole is drilled through the center of a sphere. The cylinder-with-caps is removed. The length of the r...

Nicole Immorlica reports on the NSF CISE Broader Impacts Summit held last week in DC. We've all seen it. Most of us have even written...

Some random thoughts about quiz shows. THOUGHT ONE: There could be a quiz show based on P and NP. We all think that FINDING an answer is...

There was a Women in Theory Workshop at Princeton From June 19-23. ***SORELLE***, who was there, has some intelligent and interesting t...

How to best describe what we do to the layperson? It depends on what you mean by layperson . I was in Austin Texas visiting my nephew Ja...

I set up a new blog, Future of STOC to discuss role of our main conference and how to achieve it. At STOC this year we had a relatively l...