Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISPERSER:
Reports tagged with disperser:
TR05-100 | 30th August 2005
David Zuckerman

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>


TR10-064 | 13th April 2010
Xin Li

A New Approach to Affine Extractors and Dispersers

We study the problem of constructing affine extractors over \mathsf{GF(2)}. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>


TR15-121 | 25th July 2015
Xin Li

Extractors for Affine Sources with Polylogarithmic Entropy

We give the first explicit construction of deterministic extractors for affine sources over F_2, with entropy k \geq \log^C n for some large enough constant C, where n is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>


TR22-109 | 27th July 2022
Siddharth Iyer, Michael Whitmeyer

Searching for Regularity in Bounded Functions

Given a function f:\mathbb F_2^n \to [-1,1], this work seeks to find a large affine subspace \mathcal U such that f, when restricted to \mathcal U, has small nontrivial Fourier coefficients.

We show that for any function f:\mathbb F_2^n \to [-1,1] with Fourier degree d, there exists an affine subspace ... more >>>


TR24-040 | 29th February 2024
Kuan Cheng, Ruiyang Wu

Randomness Extractors in \mathrm{AC}^0 and \mathrm{NC}^1: Optimal up to Constant Factors

Revisions: 1

We study extractors computable in uniform \mathrm{AC}^0 and uniform \mathrm{NC}^1.

For the \mathrm{AC}^0 setting, we give a construction such that for every k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}, it can extract (1-\gamma)k randomness from an (n, k) source for an arbitrary constant ... more >>>




ISSN 1433-8092 | Imprint