## Thursday, November 13, 2014

### From Homework Solution to Research Paper

Inspired by the Dantzig Story  I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving a homework question the hard way.

Teaching in the early 90's, I showed Valiant's proof that computing the permanent of a 0-1 matrix was #P-complete, including showing that the 0-1 permanent was in #P, the class of functions representable as the number of accepting paths of a nondeterministic polynomial-time Turing machine.

I gave a homework assignment to show that the permanent of a matrix with non-negative integer entries was in #P. The answer I expected was to construct an appropriate NP machine whose number of accepting paths equalled the permanent and some students came up with such a proof.

One of the students Viktória Zankó took a different approach, creating a reduction that mapped an integer matrix A to a 0-1 matrix B such that permanent(A) = permanent(B). A fine solution reducing the problem to a previously solved case.

So what's the rub? Such a reduction was an open problem and simplified Valiant's paper. Valiant only had the reduction for integer matrices A with small entries and needed a mod trick to show the 0-1 permanent is #P-complete. Zankó's construction eliminated the need for the mod trick.

And that's how Viktória Zankó got a research paper from solving a homework problem.

1. I knew this paper but not the story behind it, thanks!

2. This blog post is essentially a duplicate of a previous post, see: http://oldblog.computationalcomplexity.org/archive/2003_03_01_archive.html , in particular the entry from March 14, 2003.

1. You have a better memory than I do. I did a search for Zanko before I wrote today's post but "Zanko" didn't match "Zankó". Sorry for the duplicate and hopefully those who are newer to my blog find this post interesting.