On approximate Horn minimization

Gyorgy Turan

(Univ. of Illinois at Chicago and Univ. of Szeged)

It is known that minimizing Horn formulas is NP-hard, but

the problem has an efficient O(n)-approximation algorithm,

where n is the number of variables. We consider lower and

upper bounds for the approximability of different versions.

Joint work with Amitava Bhattacharya, Bhaskar DasGupta and

Dhruv Mubayi.