Under the auspices of the Computational Complexity Foundation (CCF)

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

ISSN 1433-8092 | Imprint