ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05, 06, 15, 20, 94 Strazdins, Indulis, Riga Technical University, Latvia Universal classification of Boolean functions by the affine and linear groups For the groups of affine and linear transformations we propose a new classification of Boolean functions, building a tree of minimal representatives of types (orbits), as well as determining spectral invariants and stabilizer orders. The types are arranged into a unique infinite sequence irrespectively of the number of variables. More than 300 first entries of both tables are computed. Also the first variant (totally asymmetric) functions are found. Apart from synthesis of switching circiuts, this classification can be used in the study of regular combinatorial structures described by incidence matrices: block designs, graphs, and codes. Reference: I. Strazdins, Universal affine classification of Boolean functions, Acta Appl. Math. 46 (1997), No. 2, 147–167.