Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Seminar Approximate Methods in Geometry (263-4201-00L) HS08

This seminar will be held in English.

Bernd Gärtner, CAB G32.2, Tel: 01-632 70 26, lastname@inf.ethz.ch.
Uli Wagner, CAB G33.2, Tel: 01-632 73 39, lastname@inf.ethz.ch.
Emo Welzl, CAB G15.2, Tel: 01-632 73 70, lastname@inf.ethz.ch.

Contents

This seminar is held once a year and complements the course ``Approximate Methods in Geometry''. Participation (exam passed) in one of the courses ``Algorithmische Geometrie'' or ``Approximate Methods in Geometry'' is necessary as a prerequisite. Students of the seminar will present original research papers on approximate methods in geometry, most of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area. This seminar is geared towards topics that are typically covered in a course like ``Approximate Methods in Geometry''. In the Spring semester, we offer a similar seminar geared towards topics around the course ``Computational Geometry''.

Dates

First meeting: Friday, September 19, 2008 13:00-15:00, CAB G52.
The plan is to hold the seminar as a block seminar on two to three Fridays during the semester (dates to be agreed upon during first meeting).

Proposed papers

  1. J. Matousek, On variants of the Johnson-Lindenstrauss Lemma, Random Structures and Algorithms 33(2) (2008) [DOI]
  2. B. Chazelle, D. Liu, and A. Magen, Approximate Range Searching in Higher Dimensions, Computational Geometry - Theory and Applications 39(1) (2008), 24-29 [DOI]
  3. N. Ailon and E. Liberty, Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes, Proc. 19th annual ACM-SIAM symposium on Discrete algorithms (SODA), 1-9 (2008) [HTML]
  4. E. Liberty, N. Ailon and A. Singer, Dense Fast Random Projections and Lean Walsh Transform, Proc. RANDOM 2008 (to appear) [PDF]
  5. T. Martinetz, A. Madany Mamlouk, and C. Mota, Fast and Easy Computation of Approximate Smallest Enclosing Balls, Proc. Brazilian Symposium on Computer Graphics and Image Processing (2006) [PDF]
  6. T. Chan, Dynamic Coresets, Proceedings 24th annual symposium on Computational geometry (SCG), 1-9 (2008) [HTML]

Conditions

A successful participation in the seminar requires the following:
  1. previous participation (exam passed) in one of the courses ``Algorithmische Geometrie'' or ``Approximate Methods in Geometry'';
  2. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  3. a satisfactory plenary talk;
  4. attendance at all other talks.
Important: Please also consult and follow our seminar guidelines.