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
Lincoln's Dog-Tail question (in honor of Presidents Day)
(Posted in Honor of Presidents Day.) The following is NOT a trick question; however, I have heard two different answers for it. How many legs would a dogPlay...
From Computational Complexity
CCC 2011 papers- you heard it here first
The complexity papers for CCC 2011 are posted HERE. (They might not be at the official CCC site yet; however, I have permission to post here.) Kudos to Omer....
From Computational Complexity
If I tweeted here is what I would tweet
If I tweeted there is what I would tweet: There was an interesting blog post that responded to Aaron Sterling's Chemoinformatics Post. See here for this interesting...
From Computational Complexity
PROS and CONS of being on a Program Committee
What are the PROS and CONS of being on a program committee? PRO: Looks good on your resume. Is this true at your school? This PRO may be more relevant forunturned...
From Computational Complexity
STOC 2011 accepte papers posted.You heard it here...12th!
For those who did not read yesterdays comments or Lance's Tweet (the empty set?) the list of accepted STOC papers is here. 84 papers accepted. I personallygrow...
From Computational Complexity
All the news that fit to tweet
The Daily Shows Slogan used to be When news break we fix it! This raises the question: When does breaking news actually break? (My memory of this may be hazy...
From Computational Complexity
Is Cheminformatics the new Bioinformatics? (Guest Post by Aaron Sterling)
Chemoinformatics for Computer Scientists Guest Post by Aaron Sterling I recently completed a review of Handbook of Chemoinformatics Algorithms (HCA)here...
From Computational Complexity
Does Tiger Woods know what Venn Diagram is?
In prior blogs I noted that the terms Turing Test and Prisoner's Dilemma have been used in articles for non-math people. In the age of Google people can look...
From Computational Complexity
Are you a Ringer? A Reverse Ringer?
A ringer is an impostor, especially one whose pretense is intended to gain an advantage in a competition. This definition is from Wikipedia and agrees with what...
From Computational Complexity
LICS and TAMC call for papers
Two Call For Papers Announcements: LICS 2011 (Logic in Computer Science) has posted its call-for-papers here. (It was probably posted a while back- the submission...
From Computational Complexity
What is a breakthrough? Lets have an intelligent discussion!!!!!!
In 2010 this blog announced the following Breakthrough!!!! results: (Listed chronologically.) Better Algorithms for Unique Games, by Arora, Barak, Steurer. (We...
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