Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander E. Andreev:

TR00-053 | 5th May 2000
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim

Parallel Read Operations Without Memory Contention

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

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

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

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

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

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

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

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

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

TR95-061 | 27th November 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting sets derandomize BPP

Revisions: 1

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

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

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

ISSN 1433-8092 | Imprint