Beyond Worst-case Analysis of Various Algorithms

In recent year, theory and practice in computer science has steered away from each other in many aspects. Recent improvements in computational capabilities and field of optimization have seen rise to the use of various different heuristics, which work in practice with great success, but have not seen much investigation on the theory side. This has created a need for theoretical investigation to bridge the gap between two branches of computing. More frequently than not, the heuristic choices relies on known empirical observations, and intuitive understanding of trade-off between runtime, memory, quality of approximation and probability of success of these algorithms. In this thesis, we discuss a few such interesting dilemmas, and try to provide provable justifications for some of them by using various probabilistic and analytical techniques. We will focus on two main topics - average-case approximation quality of various lower bounds used for Euclidean Traveling Salesman Problem and computational versus statistical efficiency of modern generative models, like noise contrastive estimation and score estimation.