The complexity of some topological inference problems (Q486691)

The author gives some lower bounds on the description, sample and computational complexities of the problems of computing dimension, homology and topological type of a manifold, and detecting singularities for a polyhedron. The paper appears in the following structure: Section 1 is entitled ``Statement of results'' and contains: 1.1 Problem 1: dimension; 1.2 Problem 2: topological types; 1.3 Problem 3: singularities. Then, in Section 2, the author gives the proofs for the three problems. In Section 3 he discusses the implications of the obtained results. In addition to other observations, he remarks that the results given in this paper have a negative air: some very natural problems have very large (e.g. superexponential) complexity when measured in various ways. Finally he emphasizes that his view is that the results of the paper should help to guide researchers who wish to apply geometric topological tools. An interesting and instructive paper.