Prof. Micha Sharir (michas@post.tau.ac.il)

**Fall 2015, Monday 14:00-16:00, Shenkar--Physics 204 **

**
Announcements:
**

The material is taken from Sariel Har-Peled's book
on Geometric Approximation Algorithms.

Additional material, if needed, will be distributed during the seminar.

The following partition of the material into talks is fixed for now, but
may be updated as time goes by.

The dates towards the end are *incorrect* -- We will have one or two Fridays in addition, and talks will shift

(Apologies for any misspellings of family names...)

__ Assignments: __

**Talk 1: **

*Speaker: Yuval Bertocchi *, 2.11.15

Material: Chapter 1, The power of Grids

** Slides **

**Talk 2: **

*Speaker: Ariel Litmanovich*, 9.11.15

Material: Chapter 2: Quadtrees

** Slides **

**Talk 3: **

*Speaker: Barak Steindl*, 16.11.15

Material: Chapter 3: Well separated pairs decomposition

** Slides **

**Talk 4: **

*Speaker: Nadav Kareen*, 23.11.15

Material: Chapter 4: Clustering

** Slides **

**Talk 5: **

*Speaker: Matan Liber*, 30.11.15

Material: Chapter 5a: Complexity, sampling, epsilon-nets and
epsilon-samples

** Slides **

**Talk 6: **

*Speaker: Mor Levi*, 7.12.15

Material: Chapter 5b: Complexity, sampling, epsilon-nets and
epsilon-samples

** Slides **

**Talk 7: **

*Speaker: Sofia Rubinsky*, 14.12.15

Material: Chapter 6: Approximation via reweighing

** Slides **

**Talk 8: **

*Speaker: Sveta Oksan*, 21.12.15

Material: Chapter 8: Sampling and the moments technique

** Slides **

**Talk 9: **

*Speaker: Eitan-Hai Mashiach*, 28.12.15

Material: Chapter 9: Depth estimation via sampling

** Slides **

**Talk 10: **

*Speaker: Shirly Yakubov*, 4.1.16

Material: Chapter 10: Approximating the depth via sampling and emptiness

** Slides **

**Talk 11: **

*Speaker: Idan Attias*, 11.1.16

Material: Chapter 11: Random partition via shifting

** Slides **

**Talk 12: **

*Speaker: Roie Salama*, 13.1.16, Schreiber 210, 15--17

Material: Chapter 19: Dimension reduction: The Johnson-Lindenstrauss Lemma

** Presentation **