Computational Complexity

The pandemic hampered many activities but research flourished with a number of great results in complexity. Result of the year goes to Local...

I have a new article Fifty Years of P vs. NP and the Possibility of the Impossible , to mark the anniversary of the 1971 publication of Stev...

 (I abbreviate Fibonacci by Fib throughout. Lane Hemaspaandra helped me with this post.)  We all learned that Fib invented or discovered the...

When the Wall Street Journal's editorial board  and the New York Post endorse your efforts, that should ring warning bells. Several mem...

(Guest Post by Hunter Monroe) In this  guest post and  discussion paper , I present a remarkable set of structurally similar conjecture...

Guest Post from Paul Beame on behalf of the TheoretiCS Foundation I am writing to let you know of the launch today of TheoretiCS , a new ful...

 I have  co-authored (with Nathan Hayes, Anthony Ostuni, Davin Park) an open problems column  on the topic of this post. It is  here . Let g...

Suppose you have a non-empty subset S of {1,...N} and want to find an element of S. You can ask arbitrary questions of the form "Does S...

Back in March of 2019 I wrote I was also going to post about Yann LeCun's Facebook rant about stodgy CS departments but then Yann goes a...

 I posted on  When did Math get so hard?  a commenter pointed out that one can also ask  When did Computer Science Theory Get so Hard? For t...

Twenty years ago DIMACS hosted a  Workshop on Computational Issues in Game Theory and Mechanism Design . This wasn't the very beginning ...

  I trust Evangelos Georgiadis to do a guest post on Trust and Blockchain.  Today we have a guest post by Evangelos Georgiadis on Trust. It ...

Complexity is at its best when it models new technologies so we can study it in a principled way. Quantum computing comes to mind as a good ...

I have been on many Math PhD thesis defense's  as the Dean's Representative. This means I don't have to understand the work, ju...

We're in the midst of a great transformation in computing, one where data takes center stage and I predict this will start to have a lar...

The problem of squaring the circle : Given a circle, construct (with straightedge and compass) a square with the same area. While browsing t...

(This post was inspired by Harry Lewis emailing me about his granddaughter.) Harry Lewis's grand daughter Alexandra Fahrenthold (see bot...

When László Babai first announced his graph isomorphism in quasipolynomial time result, I wrote We think of theory as a young person's g...

Lance : How come you haven't blogged on your muffin book? You've blogged about two books by Harry Lewis (see here  and  here ) one b...

Potbelly, a local sandwich chain, made me an offer I couldn't refuse: change my password and earn a free (and quite tasty) oatmeal choco...