期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The efficient construction of Hitting Sets for non trivial classes
of boolean functions is a fundamental problem in the theory
of derandomization. Our paper presents a new method to efficiently
construct Hitting Sets for the class of systems of boolean linear
functions. Systems of boolean linear functions
can be also considered as the algebraic generalization of boolean
combinatorial rectangular functions studied by Linial et al.
In the restricted case of boolean rectangular functions, our method
(even though completely different) achieves equivalent results to
those obtained by Linial et al. Our method gives also an interesting
upper bound on the circuit complexity of the solutions of any
system of {\em linear equations} defined over a finite field.
Furthermore, as preliminary result, we show a new upper bound
on the circuit complexity of integer {\em monotone} functions
that generalizes the upper bound previously
obtained by Lupanov.
