THE COMPLEXITY OF FINITE FUNCTIONS
Boštjan Vilfan · DSpace@MIT (Massachusetts Institute of Technology) · 1972
Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length {0,...,d-1} of f which, is representable by special class of formulas called homogeneous e-complexes.