Mini-Project on Embeddings of Graphs
ScheduleWed. 12:00-14:00, Bldng 90, Class 223.
OutlineThe aim of this mini-project is to familiarize students with the area of Low-distortion Embeddings of graphs. The students will be required to read a paper or two on this subject, to implement an algorithm described in this paper, and to experiment with this algorithm.
General informationAfter the first meeting that will serve as an introductory lecture, the class will meet once in three weeks. On the first meeting the assignment of papers to pairs of students will take place. Each consequent meeting will be devoted to status update: each project team will describe its progress, and its problems. These update meetings will have double goal: first to help the pairs that are stuck to advance, and second to evaluate the progress of each pair. The last meeting will be devoted to presentations of the final projects.
The grade will be composed from: 60% evaluation of the final project, and 40% evaluation of the progress of the pair throughout the semester.
All the correspondence between the students and the lecturer should be conducted through email; phone calls should be used only for very urgent affairs, or if the lecturer failed to answer student's email within a period of one week (hopefully, this won't happen).
J. Graph Theory, 13 (1989), pp. 99--116
Discrete Comput. Geom., 9 (1993), pp. 81--100.
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 503--513.
Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 648-658,1993
Proc. of the 30th International Colloq. on Automata, Languages and Computing, ICALP 2003, pp. 284-296
SIAM J. Comput., 24:78-100, 1995.
Proc. 37th IEEE Symp. on Foundations of Computer Science, pp. 184-193, 1996.
SIAM J. Comput. 33(3): 608-631 (2004)