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
Do you support CCC's declaration of Ind? If so...
The steering committee for the CCC recently announced its decision to be independent of IEEE. Here is their open letter to that effect. If you agree with thishere...
From Computational Complexity
Law of small numbers and letters
The law of small numbers is that there are not enough small numbers for all of the tasks that are assigned to them. That makes some math cranks find patterns which...
From Computational Complexity
Review of People, Problems and Proofs By Lipton and Regan
(A version of this either already has or well appear in SIGACT NEWS book rev column.) A review of the blog-book PEOPLE, PROBLEMS, AND PROOFS by Richard Lipton...
From Computational Complexity
''4col \le 3col is counter-intuitive and makes me sad'' NOT ANYMORE!
In my ugrad theory class (reg,P,NP,Dec,c.e) I proved that SAT is NP-complete. In the next lecture I proved that SAT \le 3-col, so 3-col is NP-complete. I thenLeast...
From Computational Complexity
How should qualifying exams and courses work
In my last post about what Every Theory Grad Student Should know some more general questions were raised: Qualifying exams vs Course Requirements. Why do we have...
From Computational Complexity
Every Theory Grad Student should know...
This semester my Graduate Complexity Course has nine students in it. It had not been offered for two years (when it had around 20) so the demand, such as it is,...
From Computational Complexity
The Big bang Theory hits close to home
On a recent episode of The Big Bang Theory Sheldon gives up String theory because, after working on it for 20 years, he has nothing to show for his efforts. Icompactify...
From Computational Complexity
Changing the ORDER you teach things in might help A LOT
I am teaching the undergrad jr/sr course Elementary Theory of Computation which is Reg Langs, Context free Langs, Computability theory, P and NP. Over the last...
From Computational Complexity
Factorization in coNP- in other domains?
I had on an exam in my grad complexity course to show that the following set is in coNP FACT = { (n,m) : there is a factor y of n with 2 \le y \le m } The answer...
From Computational Complexity
How free is Randomness?
Matthew Green had a great post on the topic how do you know a random number generator is working. Gee, I just look at the sequence and see if it LOOKS random. ...
From Computational Complexity
How I learn a result
There is a theorem I want to learn. How do I go about it? (How do YOU go about it?) I give an example here which also leads to pointers to some mathematics ofhere...
From Computational Complexity
The answer is either 0,1, or on the board
I have heard (and later told people) that the in a math course if you don't know the answer you should guess either 0 or 1 or something on the board. This works...
From Computational Complexity
Leslie Lamport wins Turing Award!
Leslie Lamport wins Turing Award! See here for more details. Leslie did work on reliability of systems and security that (according to the article) is ACTUALLY...
From Computational Complexity
Why do we think P NE NP? (inspired by Scott's post)
Recently Scott Posted an excellent essay on reasons to think that P NE NP. This inspired me to post on the same topic. Inspired is probably the right word. Some...
From Computational Complexity
Why are there so few intemediary problems in Complexity? In Computability?
There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are in NP-P but are NOT NPC? Some candidates are Factoring...
From Computational Complexity
When is a paper public? When is anything public?
A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper public? I didn't think about...
From Computational Complexity
Maryland looking for a Lecturer/Who teachers your intro courses?
My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right now. I think he overestimates the power of this...
From Computational Complexity
Superbowl underdogs and overdogs
(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a `big game sale on beer'...
From Computational Complexity
Contribute to the Martin Gardner Centennial
Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here. I left a comment there, but I expand it for...
From Computational Complexity