Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Friday, January 22, 2021

Alan Selman (1941-2021)

›
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...
Thursday, January 21, 2021

Presidential Quiz: Three ways to take it

›
 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...
Tuesday, January 19, 2021

The Ethics Board

›
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...
2 comments:
Sunday, January 10, 2021

The ACM History Committee call for proposals looks wrong

›
 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 ...
12 comments:
Tuesday, January 05, 2021

My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!

›
 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...
5 comments:
Thursday, December 31, 2020

Complexity Year in Review 2020

›
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...
2 comments:
Thursday, December 24, 2020

Slowest Sorting Algorithms

›
Radu Gigore  tweeted  "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift...
12 comments:
Sunday, December 20, 2020

Dr Jill Biden

›
(I was helped on this post by Gorjan Alagic, Andrew Childs,  Tom Goldstein, Daniel Gottsman, Clyde Kruskal,  Jon Katz. I emailed them for th...
12 comments:
›
Home
View web version
Powered by Blogger.