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
BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!
BREAKTHROUGH in Algorithms: Improved Algorithm for Metric TSP, (Guest Blog by Mohammad Hajiaghayi) We all recently heard about the breakthrough complexity...
From Computational Complexity
Low, Superlow, supersuperlow sets, and Paywalls
Recall the following: If A is a set then A' (pronounced 'A jump') is the halting set relative to A. Formally it is: { e | MeA(e) converges } A set A is ...
From Computational Complexity
Math- Old School
In the last month we have reported on NEW RESULTS by Williams, Katz and Guth, Sanders, and Pinkerton and Setra. For a change of pace lets look at some really OLD...
From Computational Complexity
46 lunches free lunches!
(CONGRADS to all the new ACM fellows. Among them are theorists Jennifer Chayes, Anne Condon, Phil Klein, S. Muthu, and Dan Spielman.) In my post about mentoring...
From Computational Complexity
A BREAKTHROUGH result on density and 3-AP's
We use the following terminology: [n] means the set {1,...,n}. k-AP means an arithmetic progression of length k. A 3-free set is one with no 3-AP.s in it. We use...
From Computational Complexity
Erdos Distance Problem SOLVED!
(All papers referred to in this post can be accessed from my website on the Erdos Distance Problem.). In 1946 Erdos raised the following question: Given n points...
From Computational Complexity
Eleven Tweets from GASARCH
I don't do tweets-I don't think I have enough interesting 140-char notes to tell people (though that doesn't stop Lance). However, several tweet-worthy notes did...
From Computational Complexity
A Problem with Wikipedia and the Next Best Thing to Winning a Godel Prize
(There are TWO theory day events in NY this semsester: Nov 11, 2010 and Nov 12, 2010. The first one has likely already started as you read this.) I searched...
From Computational Complexity
A non rigorous proof technique
As a grad student (1980's) I found a book in the library that claimed to solve Fermat's Last Theorem using elementary methods. (This was before Wiles had shownhere...
From Computational Complexity
The revolution will be DVRed
(There are TWO theory day events in NY this semester: Thu Nov 11. and Fri Nov 12.) BILL: Will you be going to the RALLY TO RESTORE SANITY AND/OR FEAR? (Seehere...
From Computational Complexity
Advice on getting connecting to the community (guest post by Daniel Apon)
(Guest Post by Daniel Apon.) As a follow up to the last post on Do Conferences Build Community? I offer some advice for people to get connected to the community...
From Computational Complexity
Do conference build community? (joint post)
(Joint Post by Daniel Apon and Bill Gasarch. Does doing joint posts build community?) In GASARCH's post on Will there be a 50th CCC He mentioned that conferences...
From Computational Complexity
New York Area Theory Day- Nov 12, 2010
New York Area Theory Day, Organized by: IBM/NYU/Columbia, External sponsorship by: Google, Friday, November 12, 2010 The Theory Day will be held at Couranthere...
From Computational Complexity
Will there be a 50th CCC? Will you be there?
At the 25th CCC Juris Hartmanis gave a great talk to celebrate having a 25th. Will there be a 50th? I asked people at the conference. What did they say? Watch the...
From Computational Complexity
How hard is this problem?- I ask this non-rhetorically
I recently saw the following puzzle: Which two numbers come at the end of this sequence? (That is, what are x and y?) 2,4,5,30,32,34,36,40,42,44,46,50,52,54...
From Computational Complexity
Two Candidates for an Ig Noble in Mathematics
(This is a sequel to my post on the Ig Nobel Prize.) Two candidates for an Ig Nobel prizes in Mathematics. They deserve it for opposite reasons. (They are old...
From Computational Complexity
Noble and Ig Noble Prizes
What is the Ig Nobel prize? To quote the website: The Ig Nobel Prizes honor achievements that first make people laugh, and then make them think. The prizes are...
From Computational Complexity
Review of Lipton's Book-Blog/Review of Goldreich and Arora-Barak/New Book Review Column/Do you want to review?
My review of Lipton's new blog-book is here. It will appear in my SIGACT NEWS at some later time. Daniel Apon's joint review of Computational Complexity: A...
From Computational Complexity
Theorems that are less interesting because they are more interesting
(This post was inspired by Joe Kruskal's passing. Kruskal's tree theorem, trees under minor are a well quasi order, relates to example 2 below.) There are some...
From Computational Complexity