Computability in Linear Algebra (2004)

What I find quite interesting to think about is how the complexity (as a function of accuracy) of a “taken-for-granted” computational process works in the context of another process. For example, the eigensystem of its adjacency matrix provides powerful understanding of a graph — but how much accuracy do you need in order to trust that understanding? If you need arbitrary precision because of the pathological features of a particular family of graph (expander graphs, say), and the scaling of the needed precision links directly to aspects of that graph pathology, this is really telling you that the eigenvector computation is not the most natural “computation basis” to approach this phenomenon — and some explicitly discrete algorithm would make this latent complexity relationship manifest. Probably individual instances of this kind of phenomena are well known to those who study the relevant structures, but I’m not sure if the general phenomena is described or modeled anywhere.

In some weird sense you can link this to a kind of “computational curvature” — ala some of Wolfram’s metamathematical musings. If one’s prior is to distrust continuous mathematics and see only discrete computational processes as “real”, it’s exactly the kind of phenomena one will be on the lookout for. Anyway, the curvature analogy is that as you attempt to maintain a particular computational basis for computing a phenomena of interest as its complexity scales, other typically-uncorrelated complexity requirements that are normally treated as constants will explode. Needs to be made more concrete though.