All reports by Author Jose' D. P. Rolim:

__
TR00-053
| 5th May 2000
__

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim#### Parallel Read Operations Without Memory Contention

__
TR97-053
| 10th November 1997
__

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim#### Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

__
TR97-029
| 20th August 1997
__

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger#### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

__
TR96-055
| 22nd October 1996
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Hitting Properties of Hard Boolean Operators and their Consequences on BPP

Revisions: 1
,
Comments: 1

__
TR96-029
| 16th April 1996
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Towards efficient constructions of hitting sets that derandomize BPP

__
TR95-061
| 27th November 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Hitting sets derandomize BPP

Revisions: 1

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim

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

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

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

more >>>

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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.

...
more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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