Complexity, Algorithms, Programs, Systems: The Shifting Focus

We investigate the changing relationship between the small research community of theoretical computer scientists and the much larger community of computer users, in particular, the technology transfer problem of how to exploit theoretical insights that can lead to better products. Our recommendation can be summarized in four points: 1 The computing community is impressed by usable tools and by little else. Although a powerful theorem or ån elegant algorithm may be a useful tool for a fellow theoretician, by and large, the only tools directly usable by the general computing community are systems. No systems, no impact! 2 System development means programming-in-the-large, but the algorithms research community so far has learned only how to program in-the-small. 3 Algorithm researchers must enshrine their algorithms not merely in individual elegant programs, but collectively in useful application packages aimed at some identifiable user group. 4 Since the development of software systems easily turns into a full-time activity that requires different skills from those of algorithms research, we must strive to develop techniques that lets a small group of algorithm researchers develop simply structured, open-ended systems whose kernel can be implemented with an effort of the order of 1 man-year. Low-complexity systems is the goal!