The unpredictable deviousness of models

AbstractComputation models are central to algorithmic research. A model, designed to capture the essential features of a technology dispensing with irrelevant and burdensome details, is a judicious compromise between simplicity and fidelity (or reflectivity). This approach has unleashed an enormous amount of valuable algorithmic research over the years. However, the pursuit of simplicity may filter out details, once deemed irrelevant, which may later reassert their significance under either technological pressure or more careful scrutiny, in which case the inadequacy of the model cripples the validity of the derived results. Examples of this situation, drawn from computational geometry, numerical parallel computation, VLSI theory, and computational biology, will be reviewed and examined in detail