Computational Complexity

 (Thanks to James De Santis for pointing the article that inspired this post on Post. The article is pointed to in this post.) What is Emil ...

September Edition Who thought the algorithm behind machine learning would have cool complexity implications? The Complexity of Gradient Desc...

 ( I had a post a while back requesting people to submit open problems in Luca Trevisan's honor with deadline Oct 1. I am extending that...

I often do  LeetCode  problems for fun. This site mainly provides short coding problems for students and others to train for the kinds of qu...

 On Page 75 of  The Existential Theory of the Reals as a Complexity Class: A Compendium by Marcus Schaefer, Jean Cardinal, Tillmann Mitzow (...

Last week I walked around the  International Manufacturing Technology Show  with 89,000 other participants at the McCormick Center in Chicag...

LANCE: I gave my final exam for my ugrad theory course (regular, Context Free, P, NP, Decidable, Undecidable) to the new ChatGPT o1 that cl...

If there's a position where I differ from most other complexity theorists it's that I don't believe that natural proofs present ...

Someone once told me:  I was not surprised when Linear Programming was in P since it was already in \(  NP \cap  coNP  \), and problems in t...

August Edition A quasipolynomial-time algorithm for a long standing open problem. Yes, we have two of them this decade. Deciding Parity Gam...

There is a paper (see  here  for an article about the paper, the link to the paper itself is later) that claims to PROVE that, on average, t...

Rendering of PsiQuantum's facility in Chicago I wasn't looking for quantum this summer but it found me. At various events I ran into...

At the Trump-Musk interview: 1) There were technical difficulties which caused it to start late and have some other problems. 2) Musk and (I...

Earlier this summer I attended a Celebration for Leonid Levin who recently turned 75. To prepare my talk I wanted to go back to Levin's...

 Request for Open Problems In Memory of Luca Trevisan ADDED LATER: DEADLINE EXTENDED TO OCT 14 BUT THAT IS A VERY VERY HARD DEADLINE.  Luca ...

July Edition This months favorite theorem is a circuit result that implies the polynomial-time hierarchy is infinite relative to a random or...

 (Inspired by Pat Sajak stepping down from Wheel of Fortune) How many different game show are there? Many. How many could there be? 1) Based...

 I was wondering what the hardest math problems were, and how to define it. So I googled  Hardest Math Problems The first hit is  here . The...

In response to my blog post about how its easier to FIND novelty songs (and other things) than it used to be (see  here ) Lance showed how e...

Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets, 2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasan ...