Computational Complexity

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

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 ...
10 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:
Wednesday, December 16, 2020

Optiland

›
Many of you have heard of Russell Impagliazzo's five worlds from his 1995 classic  A personal view of average-case complexity  In short...
10 comments:
Saturday, December 12, 2020

Quarterly Th. Wksp `at' Northwestern, and thoughts inspired by it

›
 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  ...
4 comments:
Wednesday, December 09, 2020

Shuffling Around

›
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...
6 comments:
›
Home
View web version
Powered by Blogger.