Computational Complexity

In the fall, I write a jobs post predicting the upcoming CS faculty job market and giving suggestions and links. In the spring I used to cro...

 (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...