Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DETERMINISTIC EXTRACTORS:
Reports tagged with Deterministic Extractors:
TR05-108 | 28th September 2005
Ariel Gabizon, Ran Raz

Deterministic Extractors for Affine Sources over Large Fields

An $(n,k)$-affine source over a finite field $F$ is a random
variable $X=(X_1,...,X_n) \in F^n$, which is uniformly
distributed over an (unknown) $k$-dimensional affine subspace of $
F^n$. We show how to (deterministically) extract practically all
the randomness from affine sources, for any field of size larger
than $n^c$ (where ... more >>>


TR05-109 | 28th September 2005
Ariel Gabizon, Ran Raz, Ronen Shaltiel

Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that
there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly
distributed and independent of each other, and the remaining $n-k$ variables
are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n
\ar \B^m$ which on ... more >>>




ISSN 1433-8092 | Imprint