Computational Complexity

 In 2013 I wrote a blog to celebrate Lance's 50th birthday by contrasting what things were like when Lance was 10 to when he was 50. Tha...

Why do we have two complexity classes for exponential time, E and EXP? First the definitions: E is the set of problems computable in time \(...

As you all know Luca Trevisan, a Giant in our field, passed away at the too-young age of 52. See Lance's post on Luca HERE.  As the edit...

Complexity theorist  Luca Trevisan  lost his battle to cancer yesterday in Milan at the age of 52. A terrible loss for our community and our...

I've argued that more and more we seem to live in an Optiland , a computational utopia where through recent developments in optimization...

I recently came across (by accident) the link to all of the BEATCS complexity columns from 1987 to the 2016. See HERE . (If you know a link ...

LANCE: I had my first Quanta Article published! I explore computation, complexity, randomness and learning and feeling the machine. BILL: F...

May Edition Most of my favorite theorems tell us something new about the world of complexity. But let's not forget the greatest technica...

For this post all Context Free Grammars (henceforth CFGs) are assumed to be in Chomsky Normal Form. The size of a CFG \(G\)  is the number o...

On the plane earlier this week I got around to watching the Academy Award winning movie  Godzilla Minus One , one of the best monster movies...

 The call for nominations for the Test of Time Award at FOCS 2024 has been posted  here . Eligibility and past winners are  here . Points 1)...

It started with a post from  Fermat's Library . 132 is the sum of all the 2-digit numbers made from its digits. It is the smallest such...

 After my post on different holiDAYS,  here , such as Talk like a Pirate Day , and Raegan Revor day , two other Days were brought to my atte...

Daniel Lemire wrote a blog post  Peer Review is Not the Gold Standard in Science . I wonder who was claiming it was. There is whole section ...

Bill and Darling are watching Jeopardy. DARLING: Bill, one of the categories is MATH TALK. You will kick butt! BILL: Not clear. I doubt they...

Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionab...

In the book Those Fascinating Numbers  by Jean-Marie De Konick they find interesting (or `interesting') things to say about many numbers...

April Edition A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a s...

(This post was inspired by Rachel F, a prior REU-CAAR student, emailing me wishing me a happy Star Wars Day.)   I am writing this on May 4 w...

Bullinger's post  on this blog last week focused on Vijay Vazirani's public obsession of finding a proof for the 1980 Micali-Vaziran...