*On approximate Horn minimization*

Gyorgy Turan

(

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.