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
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
Knowing some History is a good thing- Why?
(FOCS registration is open: here. Note that there are tutorials on Sat Oct 22 and the conference talks are Sun Oct 23-Tues Oct 25.) (Guest post by By Jeffery...
From Computational Complexity
Do we use Technology before its perfected? Should we?
During Hurricane Irene I lost power for about 18 hours. I was actually pleased how short this was. PEPCO (my power company) did not tell us when power would beprior...
From Computational Complexity
What inspired you to work on... whatever you work on?
Grad students often wonder how people get ideas of things to work on. The usual advice I give is (1) go to talks, (2) read papers, (3) talk to people, (4) follow...
From Computational Complexity