Given a positive number 5 E (0, 1), a subset 7/C {0, 1) ~ is a 5-Hitting Set for a class 7~ of boolean functions with n inputs if, for any function f E T~ such that Pr (f = 1) > 5, there exists an element h E 74 such that f(h) = 1. Our paper presents a new deterministic method to efficiently construct 5-Hitting Set for the class of systems (i.e. logi- cal conjunctions) of boolean linear functions. Systems of boolean linear functions can be considered as the algebraic generalization of boolean combinatorial rectangular functions, the only significative example for which an efficient deterministic construction of Hitting Sets were pre- viously known. In the restricted case of boolean rectangular functions, our method (even though completely different) achieves equivalent re- sults to those obtained in (11). Our results also gives an upper bound on the minimum cardinality of solution covers for the class of systems of linear equations defined over a finite field. Furthermore, as preliminary result, we show a new upper bound on the circuit complexity of integer monotone functions generalizing previous results obtained in (12).
['Alexander E. Andreev', 'Andrea E. F. Clementi', 'José D. P. Rolim']
Efficient Construction of Hitting Sets for Systems of Linear Functions