The Hebrew University Logo
Syllabus Metric Embedding Theory & its Algorithmic Applications - 67720
close window close
PDF version
Last update 31-08-2020
HU Credits: 3

Degree/Cycle: 2nd degree (Master)

Responsible Department: Computer Sciences

Semester: 1st Semester

Teaching Languages: English and Hebrew

Campus: E. Safra

Course/Module Coordinator: Prof Yair Bartal

Coordinator Email:

Coordinator Office Hours: Coordinate in advance

Teaching Staff:
Prof Yair Bartal

Course/Module description:
The course concerns with Metric embedding theory and its applications. This is a field which took a central place in the theory of algorithms in recent years due to its many applications.

Course/Module aims:
See learning outcomes.

Learning outcomes - On successful completion of this module, students should be able to:
Knowledge of the theory of metric embedding and its applications

Attendance requirements(%):

Teaching arrangement and method of instruction: Lecture

Course/Module Content:
Among the course topics are the following: Metric spaces, low distortion embedding, dimension reduction, low distortion embedding, embedding into normed spaces, probabilistic embedding of metrics into trees and its applications, metric Ramsey properties,, embedding of low average distortion, and nearest neighbor search.

Required Reading:

Additional Reading Material:
Matousek's book - Lectures on Discrete Geometry, Chapter 15 <;3439>
Deza-Laurent's book: Geometry of Cut and Metrics <;3442>

Course/Module evaluation:
End of year written/oral examination 0 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 100 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %

Additional information:
The course suits both Computer Science students as well as students of Mathematics. Additional
Students needing academic accommodations based on a disability should contact the Center for Diagnosis and Support of Students with Learning Disabilities, or the Office for Students with Disabilities, as early as possible, to discuss and coordinate accommodations, based on relevant documentation.
For further information, please visit the site of the Dean of Students Office.