@techreport{Elbassioni2006,
TITLE = {On the Complexity of Monotone {Boolean} Duality Testing},
AUTHOR = {Elbassioni, Khaled},
LANGUAGE = {eng},
NUMBER = {DIMACS TR: 2006-01},
INSTITUTION = {DIMACS},
ADDRESS = {Piscataway, NJ},
YEAR = {2006},
DATE = {2006},
ABSTRACT = {We show that the duality of a pair of monotone Boolean functions in disjunctive normal forms can be tested in polylogarithmic time using a quasi-polynomial number of processors. Our decomposition technique yields stronger bounds on the complexity of the problem than those currently known and also allows for generating all minimal transversals of a given hypergraph using only polynomial space.},
}