  Horn functions form a subclass of Boolean functions and appear in many
different areas of computer science and mathematics as a general tool to
describe implications and dependencies. Finding minimum sized representations
for such functions with respect to most commonly used measures is a
computationally hard problem that remains hard even for the important subclass
of key Horn functions. In this paper we provide logarithmic factor
approximation algorithms for key Horn functions with respect to all measures
studied in the literature for which the problem is known to be hard.
