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
The Conjunction Paradox
In Yesterday's post you were told about Susan: Susan is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student she was deeply...
From Computational Complexity
Rank these possibilities by probability
Readers- I want you to answer this question and post your answers as comments. I will tell you WHY I am asking tommorow. Susan is 28 years old, single, outspoken...
From Computational Complexity
Is there a NICE gadget for showing PLANAR HC is NPC?
(I have already posted this question on CS Theory Stack Exchange.) If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget...
From Computational Complexity
Romney vs. Aaronson
How are Mitt Romney and Scott Aaronson similar? Different? Similarities: Both live in Massachusetts. Actually, Scott lives there but its not clear where Mitt...
From Computational Complexity
Solution to the reciprocals problem
In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant to post this on WED...
From Computational Complexity
Is this problem too hard for a HS Math Competition
The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for an incorrect answer)....
From Computational Complexity
What is a Breakthrough?
The recent discussion on Matrix Mult inspires the general question of WHAT IS A BREAKTHROUGH? Last year I tried to get an intelligent discussion on this topic but...
From Computational Complexity
Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)
(Guest post by Ryan O'Donnell) Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean functions. I am writingBoolean...
From Computational Complexity
Matrix Mult (you heard it here... third?)
(INNOVATIONS CONFERENCE: here) (While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog...
From Computational Complexity
Are these journals real?
Consider the following email I got: Dear Professor, 1. Antarctica Journal of Mathematics 2. ArchimedesJournal of Mathematics 3. BesselJournal of Mathematics...
From Computational Complexity
My response to the Gasarch P vs NP poll
A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers. Does P=NP? IIf...
From Computational Complexity
Theorems that are impressive at first but then....
Mission Impossible was my favorite show as a kid. As an adult it would not make my top 20, and I wonder why I liked it so much as a kid. (Actually I do know- at...
From Computational Complexity
If Bill Tweeted what would he tweet (Steve Jobs Edition)
A more nuanced view of Steve Jobs: here. A less nuanced view of Steve Jobs: here. The next Steve Jobs: here A very nice NON-Steve Jobs post here. Is thisAndrew...
From Computational Complexity
If you find a mistake in someone elses paper you should....
What do you do if you read a paper or book and find mistakes in it? My first impulse is to say: Email the author. Always be polite and admit (which is true) that...
From Computational Complexity
A candidate for a new Millenium Problem
In a prior post I wrote that the Erdos-Turan Conjecture should be a Millennium problem. Today I am going to (1) suggest a generalization of the Erdos-Turan Conjecture...
From Computational Complexity
Where do theorems go to die?
(Joint post by Bill Gasarch and Daniel Apon) Recently I (Daniel) reviewed Dexter Kozen's Theory of Computation (it was AWESOME). You can find the review here...
From Computational Complexity
Conventions in Math- just to make the rules work or more?
Why is a1/2 = sqrt(a)? true? To make the rule ax+y=ax a y work out. Why is (∀ x ∈ ∅)[P(x)] true? To make the rule (∀ x ∈ A ∪ B)[P(x)] iff (∀ x ∈ A)[P(x)]...
From Computational Complexity
Guest Post on Conference Locations
(Samir Khuller Guest Post.) On Conference Locations: I recently looked at Orbitz for fares to Japan for SODA 2012 in Jan. The round trip fare from DC to...
From Computational Complexity
Next in the sequence
When I posted on sequence problems here some people said that they did not have unique answers. Many problems FORMALLY do not have a unique answer, but common sense...
From Computational Complexity