All reports by Author Andrea E. F. Clementi:

__
TR00-054
| 5th May 2000
__

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri#### On the power assignment problem in radio networks

__
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-011
| 7th April 1997
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan#### Weak Random Sources, Hitting Sets, and BPP Simulations

__
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

__
TR96-016
| 6th February 1996
__

Andrea E. F. Clementi, Luca Trevisan#### Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

__
TR95-061
| 27th November 1995
__

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

Revisions: 1

__
TR95-041
| 28th June 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim#### Optimal Bounds for the Approximation of Boolean Functions and Some Applications

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

Given a finite set $S$ of points (i.e. the stations of a radio

network) on a $d$-dimensional Euclidean space and a positive integer

$1\le h \le |S|-1$, the \minrangeh{d} problem

consists of assigning transmission ranges to the stations so as

to minimize the total power consumption, provided ...
more >>>

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

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

We show how to simulate any BPP algorithm in polynomial time

using a weak random source of min-entropy $r^{\gamma}$

for any $\gamma >0$.

This follows from a more general result about {\em sampling\/}

with weak random sources.

Our result matches an information-theoretic lower bound ...
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 >>>

Andrea E. F. Clementi, Luca Trevisan

We provide new non-approximability results for the restrictions

of the min-VC problem to bounded-degree, sparse and dense graphs.

We show that for a sufficiently large B, the recent 16/15 lower

bound proved by Bellare et al. extends with negligible

loss to graphs with bounded ...
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 >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

We prove an optimal bound on the Shannon function

$L(n,m,\epsilon)$ which describes the trade-off between the

circuit-size complexity and the degree of approximation; that is

$$L(n,m,\epsilon)\ =\

\Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$

Our bound applies to any partial boolean function

and any ...
more >>>