ALCOMFT-TR-03-45

ALCOM-FT
 

Ricard Gavald\`a and Denis Thérien
Algebraic Characterizations of Small Classes of Boolean Functions
Barcelona. Work package 4. September 2003.
Abstract: Programs over semigroups are a well-studied model of computation for boolean functions. It has been used successfully to characterize, in algebraic terms, classes of problems that can, or cannot, be solved within certain resources. The interest of the approach is that the algebraic complexity of the semigroups required to capture a class should be a good indication of its expressive (or computing) power.

In this paper we derive algebraic characterizations for some ``small'' classes of boolean functions, all of which have depth-3 \AC0 circuits, namely k-term DNF, k-DNF, k-decision lists, decision trees of bounded rank, and DNF. The interest of such classes, and the reason for this investigation, is that they have been intensely studied in computational learning theory.

Postscript file: ALCOMFT-TR-03-45.ps.gz (77 kb).

System maintainer Gerth Stølting Brodal <gerth@cs.au.dk>