Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
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...
From Computational Complexity
Sparse problems in NP thought to not be in P
(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 I was trying to make...
From Computational Complexity
Can you ever be denied Full Prof? Can you ever really fail a PhD defense.?
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 rare. These questions...
From Computational Complexity
Conflicts of Interest
a conflict-of-interest? Some thoughts. Thought One PROF: I can't vote on Professor X's Full Prof case since I have a conflict. CHAIRMAN: (There areThought...
From Computational Complexity
Jobs- who ended up where? You tell us!
Within CS theory who ended up at what jobs? Neither Lance nor I knows this. But YOU do--- collectively! So, I ask you, the readers, to leave comments about who...
From Computational Complexity
Is this solution cheating?
Consider the following problem: A hole is drilled through the center of a sphere. The cylinder-with-caps is removed. The length of the removed cylinder (itHere...
From Computational Complexity
The P vs NP quiz Show. NP! NP! NP!
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 harder than VERIFYING...
From Computational Complexity
The Lefthanded Latino Lesbians in Algebraic Topology Workshop
There was a Women in Theory Workshop at Princeton From June 19-23. ***SORELLE***, who was there, has some intelligent and interesting things to say about it...
From Computational Complexity
Talking about your work with a layperson
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 Jason. I was also giving...
From Computational Complexity
Foundational ... or simply a curiosity (Guest Post by Vijay Vazarani)
(Guest Post by Vijay Vazirani) Foundational ... or Simply a Curiosity? Conventional wisdom has it that whereas linear programs have rational solutions,...
From Computational Complexity
CCC 2010
( Reminder:Deadline for submitting to special issue of Theory of Computing in honor of Rajeev Motwani is July 30. See here. ) CCC 2010! Ran Raz gave an...
From Computational Complexity
Alternative Careers for Logicians
(Will post on Complexity next week. I am waiting until the invited talks have their slides online so that I can point to them.) Lets say you just got a PhDacademic...
From Computational Complexity
Another post on Martin Gardner
(I will post about CCC 2010 later in the week.) Several people have posted on the death of Martin Gardner: Complexity Blog (Lance) Shtetl Optimized (Scott)...
From Computational Complexity
Whats your Game Mr. Bond- The sequel!
(I will post about CCC 2010 later in the week.) The word Game is used in many different contexts within math and computer science. I list out all that a group...
From Computational Complexity