All reports by Author Kuan Cheng:

__
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

__
TR20-016
| 17th February 2020
__

Kuan Cheng, William Hoza#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

__
TR16-018
| 3rd February 2016
__

Kuan Cheng, Xin Li#### Randomness Extraction in $AC^0$ and with Small Locality

Revisions: 7

Kuan Cheng, Ruiyang Wu

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

Kuan Cheng, William Hoza

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

Kuan Cheng, Xin Li

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>>