Personal tools
You are here: Home Events Mary Cryan

Mary Cryan

A story of derandomization

I will discuss a very simple and elegant problem in complexity of (approximate) counting: the problem of counting knapsack solutions.  The status of this problem has gone through a series of interesting developments over the past couple of decades:  starting with a subexponential
randomized algorithm, to a polynomial randomized algorithm, and most recently a deterministic polynomial algorithm. (all algorithms are approximate).

Work due to many authors (not myself!)

Document Actions