acm-header
Sign In

Communications of the ACM

Blogroll


bg-corner

From Computational Complexity

Should You Mentor High School Students?

I have mentored many high school students on projects (21 in the past, 6 right now). Is this a good use of ones time? I note my experiences and advice- if you have...

From Computational Complexity

A Mathematical Urban Legend

I have heard the following story many times in many versions: A PhD student in Math at PRESTIGIOUS SCHOOL was defending his thesis which was in REALLY ABSTRACT...

From Computational Complexity

The Rubik's Cube Conjecture PROVEN! (Do we care?)

In 1994 Fermat's last theorem was proven! In 2003 Poincare's conjecture was proven! In 2010 the Rubik Cube Conjecture was proven! That is, it was shown that the...

From Computational Complexity

Intelligent questions about the alleged P NE NP proof

People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the aftermath...

From Computational Complexity

Report from Barriers II Part 1

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 that, or what a full report...

From Computational Complexity

***SORELLE*** PHD!!/Workshop on Boolean Threshold Functions/NSF program

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

From Computational Complexity

NEW math on Futurama

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 the writers who has a...

From Computational Complexity

Is Scheduling a Solved Problem? (Guest Post)

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

From Computational Complexity

Today is Paul Turan's 100th Birthday!

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

From Computational Complexity

My last post on the alleged P NE NP paper

(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 point is a retraction...

From Computational Complexity

P vs NP vs IEEE (Guest post by Paul Beame)

(Update on P vs NP: The proof uses Finite Model Theory which is sometimes called That stuff that Neil Immerman does.. Neil Immerman has found a flaw in it. See ...

From Computational Complexity

Factoring in P ?

(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 Wikipedia site that (I think) Terry...

From Computational Complexity

That P ne NP proof- whats up with that?

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 cannot do any better than...

From Computational Complexity

The Solution to the Mark-Betty Game

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

From Computational Complexity

I want your intuitions on this, so the less you know the more I want you to post

Let f(n) be a monotone increasing function from N to N. (CLARIFICATION ADDED LATER: N is the naturals.) Consider the following game: Let n be a natural number...

From Computational Complexity

What is the complexity of these problems and metaproblems?

The following problem is from Doctor Eco's Cyberpuzzles. I have shortened and generalized it. We are going to put numbers into boxes. If x,y,z are in a box then...

From Computational Complexity

This Post is Quite Different then Any You've Every Read!

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 years we wrote to you about...

From Computational Complexity

A Seventh Mil. Problem

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

From Computational Complexity

Do you want to review a book

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. YOU get a chance to look...

From Computational Complexity

Factors for getting a job- Arbitrary, random, and complex

The Job Market in Theory (likely in all of academia) has more randomness and arbitrariness (are those the same?) then people may realize. Especially young PhD's...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account