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

Program:

1. 10:00-11:00 - The sampling problem and some equivalent formulations.

**Abstract:**

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

**Abstract:**

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

**Abstract:**

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

**Abstract:**

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.

## Date:

Mon, 05/03/2018 (All day)

## Location:

Room 130, IIAS, Feldman Building, Givat Ram