Computational Complexity

Guest post by Evangelos Georgiadis Quite a few posts have recently focused on papers,publications and venues; "optimal" venues ...

Bill is out for blogging for a couple of weeks on injured-reserve (he’ll be fine). I put together a quick blog post on what’s happening in t...

The Internets are buzzing about the new paper MIP* = RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen. See po...

Lance has often said (and also in this ) that if P=NP that would be great for the world: much more efficient ways to build things, science c...

Spoiler Alert: This post has details from the final episodes of the HBO television series Silicon Valley A few times I've gotten email...

I recently needed to look at what NP problems were possibly intermediary (neither in P nor NP-complete). So I went to Wikipedia and found  t...

Some great theorems this year including non-deterministic double exponential time by quantumly entangled provers  and integer multiplication...

In my  last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context F...