Computational Complexity

From a 1994 Dagstuhl Workshop. Selman is the one wearing a cap. Alan Selman, one of the early leaders in structural complexity and the co-fo...

 Every four years around the time of the inaugural I post a presidential Quiz! I do that today, and I will post the answers on Monday.  I am...

Back in 2014 I recommended a TCS ethics board  mainly to deal with plagiarism and who should get credit for a result. It went the way of mos...

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