Computational Complexity

 In November I (and prob everyone in the ACM) got an email that was a call for proposal from the ACM History committee.  Here  is a pointer ...

 Hilbert's 10th problem is  (in modern terminology) to find an algorithm that will, given a poly  p(x1,...,xn) in Z[x1,...,xn], determin...

For the result of the year we go to all the way back to the "before times". MIP*=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidi...

Radu Gigore  tweeted  "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift...

(I was helped on this post by Gorjan Alagic, Andrew Childs,  Tom Goldstein, Daniel Gottsman, Clyde Kruskal,  Jon Katz. I emailed them for th...

Many of you have heard of Russell Impagliazzo's five worlds from his 1995 classic  A personal view of average-case complexity  In short...

 On the  Northwestern CS Theory Group  there is a set of Quarterly Theory Workshops. There is one coming up on Dec 17-18, 2020, called the  ...

In the fall of 1983 as a junior at Cornell I took CS 481, Introduction to the Theory of Computing, from Juris Hartmanis. Needless to say thi...