Computational Complexity

We sometimes hear of the (rare) scientist who fakes data or results of experiments. In theoretical computer science one cannot fake a theore...

I have heard (and later told people) that the in a math course if you don't know the answer you should guess either 0 or 1 or somethi...

It's spring break at Georgia Tech and time to head to Germany for the Dagstuhl Seminar  Computational Complexity of Discrete Proble...

Leslie Lamport wins Turing Award! See here for more details. Leslie did work on reliability of systems and security that (according to t...

During high school, well before the world-wide web with its bloggers and YouTube, out came a series Cosmos that I watched religiously. Back...

Recently  Scott Posted an excellent essay on reasons to think that P NE NP.  This inspired me to post on the same topic. Inspired is probab...

Michel Goemans and David Williamson made a splash in the 90's using semidefinite programming to give a new approximation algorithm for ...

There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are in NP-P but are NOT NPC? Some ca...

Someone took me to task because in November I posted that the CRA News had 50 pages of job ads but didn't note that very few of those a...

A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper publ...

I was 11 forty years ago when Dungeons and Dragons first appeared and by high school many of my friends spent far too many hours embarkin...

My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right now . I think he overestimat...

Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future ...

(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a...

We start the favorite theorems with a result that might surprise many is still less than ten years old. Undirected Connectivity in Log-Sp...

Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here .  I left a comment ther...

An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many othe...

A brilliant math ugrad at UMCP, Doug, is also a creative writer who wants to work on large cardinals. His creative writing may help him th...

When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apart...

YOU got into your undergrad school because not only were you good at Math but you were on the Fencing Team and in the Latin Club (so you co...