ECCC-Report TR96-029https://eccc.weizmann.ac.il/report/1996/029Comments and Revisions published for TR96-029en-usThu, 25 Apr 1996 00:59:51 +0300
Paper TR96-029
| Towards efficient constructions of hitting sets that derandomize BPP |
Alexander E. Andreev,
Andrea E. F. Clementi,
Jose' D. P. Rolim
https://eccc.weizmann.ac.il/report/1996/029 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.
Thu, 25 Apr 1996 00:59:51 +0300https://eccc.weizmann.ac.il/report/1996/029