HD-Combinatorics Special Day: Samplers in Computer Science (organized by Amnon Ta-Shma)

All talks will be given by Amnon Ta-Shma.
10:00-11:00 - The sampling problem and some equivalent formulations

11:30-12:30 - A basic "combinatorial" construction

14:00-14:45 - Algebraic constructions of randomness condensers

15:15-16:00 - Structured sampling


1. 10:00-11:00 - The sampling problem and some equivalent formulations. 
We will first define Samplers, and the parameters that
one usually tries to optimize: accuracy, confidence, query complexity
and random bit complexity. We will see how random walks on expanders
fare with this, compared with the optimal, non-explicit solution. We will
then see an almost-equivalence with randomness extractors, and state
what is known about explicit constructions of randomness extractors. We
will also see a similar equivalence between multiplicative-error
samplers and condensers.

2. 11:30-12:30 - A basic "combinatorial" construction
I will present Trevisan's extractor. We will first see an equivalence between one output bit
strong randomness extractors and list-decodable error correcting codes.
If time permits we will see how to extend this to many output bits using
ideas from pseudo-random generators (PRGs). We will also discuss a
connection between PRGs and certain type of randomness extractors
(reconstructive randomness extractors)

3. 14:00- 14:45 - Algebraic constructions of randomness condensers
We will see two algebraic constructions of randomness condensers: The GUV (Guruswami,
Umans, Vadhan) condenser using extension fields, and Zuckerman's
constant seed length somewhere random condenser building on additive
number theory. I will also mention some open problems.

4. 15:15-16:00 Structured sampling
We will mention several applications where more is required from the sampler beyond the obvious properties: Reingold's undirected connectivity in Logspace, Rozenman and Vadhan derandomized
squaring, Dinur's PCP theorem, Dinur and Kaufmann's double samplers.
Random objects do not give structured sampling, and it seems that high
dimensional expanders do give structured sampling.


Mon, 05/03/2018 (All day)


Room 130, IIAS, Feldman Building, Givat Ram