Jason (jcreed) wrote,
Jason
jcreed

Kleinberg class was impressive today. We went through a couple of problems and some surprising reductions of them.

Problem one: suppose you have some noisy bitmap image. For every pixel, you have some numbers that are like prior probabilities that they are black or white. You have a fixed number that is something like the probability that any two neighboring pixels are different. Problem: find the maximum a posteriori probability hypothesis as to what the underlying, denoised image was.

Answer: MAX FLOW/MIN CUT!

Problem two: suppose you have an undirected graph. A subgraph's (i.e. a subset of vertices') "density" is defined as the number of edges that lie entirely in it divided by the number of vertices. Find the subgraph of maximum density.

Answer: MAX FLOW/MIN CUT!

I think I had heard the first reduction before, but the second was rather surprising. Both of these problems veer very close to NP-hardness. Change the number of colors in the first problem to 3 instead of 2, and it is NP-hard. Of course the second is very close to the classic NP-hard k-clique problem.

After class went to the concert reading group meeting, where we talked about Reynolds '83. It was a huge ball of category and domain theory, but I think I understand it a little better now. We arrived at a counterexample to substantiate Reynolds's (counterexampleless) assertion in the paper that the abstraction theorem would fail if he hadn't taken certain precautions. It always feels good to fill in those little gaps and recover what the author of the paper was probably thinking.

Dinner thereafter with kw, tom, and william consisted of more type-theoretic conversation. I feel like I've been awfully productive today in socially osmosing a better understanding of my research field, even though I have no external output to show for it.
Tags: math, social
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 7 comments