Computational Complexity

Chemoinformatics for Computer Scientists Guest Post by Aaron Sterling I recently completed a review of Handbook of Chemoinformatics ...

I found the perfect CS conference. A meeting where computer scientists from all its subdisciplines come together. Not with the purpose of pr...

Guest post from Annie and Molly Fortnow Our teachers used to tell us not to use Wikipedia because anybody can edit it and therefore it isn...

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 ...

The four color theorem means you can color the United States in four colors. But can you color it in three? Try it before you read on. ...

A ringer is an impostor, especially one whose pretense is intended to gain an advantage in a competition. This definition is from Wikipedia...

Two Call For Papers Announcements: LICS 2011 (Logic in Computer Science) has posted its call-for-papers here . (It was probably posted a ...

Last Februrary Peter Wegner asked if I would be interested in writing an article for a series in ACM Ubiquity on "What is Computation?...

In 2010 this blog announced the following Breakthrough!!!! results: (Listed chronologically.) Better Algorithms for Unique Games , by Aro...

Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC 0 . The runner up is Arora, Barak and Steu...

Yesterday the Census Bureau announced the new apportionment of the 435 representatives to states based on the 2010 census. Illinois lost on...

BREAKTHROUGH in Algorithms: Improved Algorithm for Metric TSP, (Guest Blog by Mohammad Hajiaghayi) We all recently heard about the b...

Recall the following: If A is a set then A' (pronounced 'A jump') is the halting set relative to A. Formally it is: { e | M...

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 let...

(CONGRADS to all the new ACM fellows . Among them are theorists Jennifer Chayes, Anne Condon, Phil Klein, S. Muthu, and Dan Spielman.) ...

From Ryan Willams' paper : Non-uniform lower bounds establish impossibility results for computation in the physical world: it could b...

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 n...

What advantages can we get from computational hardness? Cryptography and pseudo-random number generators come to mind. But perhaps the unive...

Last week I attended the Army Research Office sponsored  Workshop on Reasoning in Adversarial and Noncooperative Environments  related to To...

(All papers referred to in this post can be accessed from my website on the Erdos Distance Problem. ). In 1946 Erdos raised the followin...