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 that the transmission ... more >>>

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

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 and solves a question that has ... 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 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 degree B. Then, we consider sparse ... 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 >>>

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 approximation degree, and thus completes the study of booleanfunction approximation, ... more >>>