Day 26

Avi Wigderson, one of the giants of computational complexity, has released a PDF draft of his new book Mathematics and Computation. The book gives a philosophical and technical overview though a number of topics in computational complexity. Definitely worth downloading and reading if you are interested in the material in this course.

Today we proved Valiant's theorem that the permanent of a matrix is #P-complete.

•  The complexity of computing the permanent by Les Valiant
• #P-Completeness Via Many-One Reductions by Viktória Zankó. This paper gives a direct reduction from permanent with exponentially large weights to the permanent of a 0-1 matrix.