# 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!)