Ramprasad S. Joshi

Associate Professor

Theoretical Computer Science, Optimization, Natural Language Processing, Computational Linguistics, Analysis of Heuristics

Degree: Ph.D. Defended the thesis "Application of Isoperimetry and Measure Concentration to Analysis of Heuristics" on 24 September 2016.

Heuristics are algorithm design strategies, intuitively conceived, empirically developed, but vaguely described and scarcely analysed. We notice, despite the apparent obscurity, that heuristics ultimately use few geometric motifs and neighbourhood structure notions. Thus, they should be amenable to analysis in settings of spaces structured by metrics and probability measures. We develop tools and techniques demonstrating this. Isoperimetry: how far we need to go to circumscribe enough search space: is a natural geometric notion useful in this analysis. The developed theory is seamlessly applicable across problem classes, discrete and continuous alike.