On the computation of the homology of semialgebraic sets

Abstract

This article describes recent advances in the computation of the homology groups of semialgebraic sets. It summarizes a series of papers by the author and several coauthors (P. Bürgisser, T. Krick, P. Lairez, M. Shub, and J. Tonelli-Cueto) on which a sequence of ideas and techniques were deployed to tackle the problem at increasing levels of generality. Our goal is not to provide a detailed technical picture. Instead, we attempt to describe the background of the problem along with a landscape of existing results, and to convey the main ideas behind both the new algorithms and their complexity analyses. (A preliminary version of this paper appeared in the book “Computing with foresight and industry”.)