Summary for public relations work

Every possible logical function can be built up from the three functions AND, OR, and NOT. For example every function that maps any sequence of 0 (false) and 1 (true) of length, say 7, to 0 or 1 is expressible as some composition of the three simple functions given above. This fact of the so-called Boolean algebra is known since times immemorial. It is the reason why computer chips can use the same electric circuits to do all sorts of computations.

Mathematicians from Linz, Dresden, Novi Sad, and Oxford together have now proved that every function from a finite set to itself can be composed from three basic functions: a sort of addition, subtraction, and some permutation of the elements of the set. It does not even matter much which permutation you choose as your third basic function. If the set is large enough, a randomly chosen permutation almost certainly will do the trick. This is just one result on which functions can be built up from a given set of simple ones - a topic that was studied extensively by our research group at the Department of Algebra at Linz.

Computing with things in a ``strange way'' is the specialty of our research group. We use abstract algebra for concrete applications. For example, how do you check which ingredients cause certain effects in paint? In the straightforward approach, you mix all possible combinations and analyze the properties of every composition. But looking at all mixtures is very costly in real life. The theory of statistical designs provides methods to obtain the effect of one of, say seven, possible substances by considering only certain combinations of these seven. It is all in how to choose this combinations - as few as possible to keep testing cheap but as much as necessary so that you can also determine the interactions among the ingredients. Because of the research project at Linz, we now know better why certain ways to choose are so efficient and we have new, easily accessible plans for testing.