We address the problem of organizing a set $T$ of shared data into the memory modules of a Distributed Memory Machine (DMM) in order to minimize memory access conflicts (i.e. memory contention) during read operations. Previous solutions for this problem can be found as fundamental subprocedures of the PRAM simulation ... more >>>

We show the following Reduction Lemma: any $\epsilon$-biased sample space with respect to (Boolean) linear tests is also $2\epsilon$-biased with respect to any system of independent linear tests. Combining this result with the previous constructions of $\epsilon$-biased sample space with respect to linear tests, we obtain the first efficient construction ... more >>>

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity ... more >>>

We present the first worst-case hardness conditions on the circuit complexity of EXP functions which are sufficient to obtain P=BPP. In particular, we show that from such hardness conditions it is possible to construct quick Hitting Sets Generators with logarithmic prize. As recently proved, i such generators can efficiently derandomize ... more >>>

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 ... more >>>

We show that hitting sets can derandomize any BPP-algorithm. This gives a positive answer to a fundamental open question in probabilistic algorithms. More precisely, we present a polynomial time deterministic algorithm which uses any given hitting set to approximate the fractions of 1's in the output of any boolean circuit ... more >>>