It was the title that caught my attention. To note, I am not an algorithmic complexity theorist, but I am interested in the application of such techniques to complexity problems arising within formal logic, especially in the presence of an induction inference. In this area, traditional complexity measures tend to give exceptionally coarse approximations of actual behavior. For the most part, this results from most logical statements used in practice only using a fragment of the expressive power. One may now see from which direction I approached this paper, and maybe why I felt there could have been a larger historical review, for example, of past attempts to go beyond worst-case analysis.

For someone focusing on algorithmic complexity, I feel this paper surveys many interesting state-of-the-art results, especially concerning the analysis of optimization problems and the simplex method. Furthermore, the author avoids deep discussion of anachronistic attempts to go beyond the ever-dominant worst-case analysis. Unfortunately for me, lacking expertise in the field, I would have enjoyed a glimpse into these historical details, for example, more than a passing reference to amortized complexity.

Skipping a discussion of all of these alternative complexity measures does make a point: in light of all the attempts, worst-case analysis is still the go-to type of analysis, even in cases when practical evidence has not completely supported its use. Note that worst-case analysis does work well in most cases, but there are classes of algorithms/problems that have been tough to thoroughly analyze. As mentioned above, the simplex method is an example of one of these algorithms where worst-case is exponential, but in practice linear time is commonplace.

For each of the various difficult-to-analyze methods covered, the author provides references and details of the analysis that confirm the behavior of the methods in practice. Thus, for algorithmic complexity theorists looking for a survey of how hard-to-analyze problems were finally tackled, this paper is a great reference. In particular, the author covers a vast array of problems, including cache replacement policies and machine learning methods. Overall, an interesting and insightful read, even if it is not what I was originally looking for.