Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-029 | 16th April 1996 00:00

Towards efficient constructions of hitting sets that derandomize BPP



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.

ISSN 1433-8092 | Imprint