Computational Complexity

Barring a surprise deal, the sequester goes into effect tomorrow. NSF Director (and soon to be CMU President) Subra Suresh announced a seque...

My darling does crossword puzzles and sometimes asks my help: Darling: Bill, Slaughter in Cooperstown - whats the answer? Bill: Enos. ...

I got a new toy this week, the Pebble watch which I got early because I pre-ordered  donated to their Kickstarter campaign. It's a li...

Recently Daniel Apon (grad student of Jon Katz at UMCP, but he also hangs out with me) proved a LOWER BOUND by proving an UPPER BOUND. His p...

Christopher Shea wrote a recent Chronicle Review article Is Scientific Truth Always Beautiful?  I would argue the answer is yes, and it boil...

STOC  and Complexity are co-located June 1-7 in beautiful Palo Alto, California. Both conferences have just announced their accepted papers...

While teaching the Equiv of DFA, NDFA, Reg exps, I wanted to impress upon my students that the best way to show DFA-langs are closed under c...

Anita Jones is troubled by the growing number of postdocs in computer science, she uses "troubling" twice in the first paragraph o...

(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research . If you are an ugra...

Mitch Daniels, the former governor of Indiana and new president of Purdue, wrote an inaugural letter  where he discusses many of the challen...

Oded Regev, Anindya De and Thomas Vidick we are about to start an online TCS seminar series. See here for details, though I have the firs...

First a word from our sponsor: Mihalis Yannakakis is celebrating his 60th birthday this year and you are invited to the party . From the E...

All of the material summazized here is in a new paper by Gasarch and Zbarsky. You can find that paper here ) Consider the following proble...

I rarely watch TV commercials anymore but its NFL playoff time and during a game last weekend, the Ford commercial showing how a liftgate ca...

Last time I taught I had to decide if I would HAND OUT the HW or just say its posted (NOTE- I post it in any case.) This may seem old fash...

You likely have not heard about the Slow Science manifesto . They don't blog. They don't tweet. They give a broken link to their Fac...

Someone in my election night party predicted Obama because: Ever since women got the right to vote (1920) if one candidate has a daughter a...

Only nine months separate the births of two very influential mathematicians, Paul Erdős and Alan Turing, whose centenaries we celebrate this...

As we turn our thoughts from Turing to Erdős , a look back at the complexity year that was. Written with help from co-blogger Bill Gasarch....

Sometimes it just takes a simple new feature in a popular piece of software to remind us how computer science just does cool stuff. Excel ...