Organization:	Peter Widmayer, Stefano Leucci and Przemysław Uznański
Teaching language:	English
Level:	Advanced BSc students
Academic Year:	Spring 2018
Dates:	Friday 23.2.2018 15:15-17.00h ETHZ CAB G 11 Saturday 07.4.2018 9:00-12:30h ETHZ HG F 26.3 Saturday 21.4.2018 9:30-16:00h ETHZ HG F 26.1 Saturday 12.5.2018 9:30-15:30h ETHZ HG F 26.3

Overview and objectives: The areas of this seminar are Algorithms and Data Structures with emphasis on modern, breakthrough results. Students learn how to critically read and study research papers, how to summarize the contents of a paper, and how to present it in a seminar.

Teaching format: Each participant writes a self-contained report of about 10 pages and gives a 30 minutes presentation (blackboard, without a computer). Each participant has a buddy. Buddies read the report, make suggestions for improvements, and help with the presentation (e.g., dry runs). The first version of the report is due three weeks before the date of the presentation, and will be discussed with the buddy and the professor about one week before the presentation. The final versions of the report are due one week before the date of the seminar.

Setup and Organization: The setup of the seminar will be discussed on Friday February 23, 2018 from 15:15 until 17:00 in room CAB G 11 at ETHZ. At the first meeting the available slots for the seminar will be distributed and papers will be assigned.

Presentations:

• Saturday 07.4.2018 9:00-12:30h ETHZ HG F 26.3
• Saturday 21.4.2018 9:30-16:00h ETHZ HG F 26.1
• Saturday 12.5.2018 9:30-15:30h ETHZ HG F 26.3

Participation at all three meetings is compulsory for students. The assessment depends on the quality of the report, presentation, active participation during the seminar, and input as a buddy.

Useful links:

• organizational slides
• How to give talks and read papers: link
• example of a good report

Schedule

Saturday 07.4.2018 (in order of presentation)

Paper	Student	Advisor	Buddy	Report
I. Althöfer, G. Das, D. Dobkin, D. Joseph. Generating sparse spanners for weighted graphs SWAT 1990	Hörmann Tierry	Stefano Leucci	Käppeli Lukas Thomas Wilhelm	report
N. Alon, Z. Galil, O. Margalit, M. Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths FOCS 1992	Signer Matteo	Przemysław Uznański	Christian Fania	report
D. Dor, S. Halperin, U. Zwick. All Pairs Almost Shortest Paths FOCS 1999	Gessler Fabian Dieter	Stefano Leucci	Li Er Lu Lawrence	report
P. N. Klein, R. E. Tarjan. A randomized linear-time algorithm for finding minimum spanning trees STOC 1994	Grob Fabian	Stefano Leucci	Mohler Jonas Oliver	report
A. Backurs, P. Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) STOC 2015	Weber Simon Lukas	Przemysław Uznański	Kaufmann Jean Martin Charles	report

Saturday 21.4.2018 (in order of presentation)

Paper	Student	Advisor	Buddy	Report
D. Bilò, L. Gualà, S. Leucci, G. Proietti Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees STACS 2016	Rimle Philipp	Stefano Leucci	Grob Fabian	report
N. Khanna, Neelesh, S. Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs STACS 2010	Käppeli Lukas Thomas Wilhelm	Peter Widmayer	Peter Emanuel Viktor	report
U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication JACM 2002	Kapfhammer Johannes Felix	Przemysław Uznański	Stampfli Timon	report
M. Parter, D. Peleg. Sparse Fault-Tolerant BFS Trees ESA 2013	Li Gengyan	Peter Widmayer	Kapfhammer Johannes Felix	report
S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, U. Zwick. Union-Find with Constant Time Deletions ICALP 2005	Rüegge Sandro Guido	Stefano Leucci	Hörmann Tierry	report
O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication FOCS 2010	Dominik Häner	Przemysław Uznański	Weber Simon Lukas	report
M. Pǎtraşcu, M. Thorup. The Power of Simple Tabulation Hashing STOC 2011	Mohler Jonas Oliver	Przemysław Uznański	Engel Lowis Anton	report

Saturday 12.5.2018 (in order of presentation)

Paper	Student	Advisor	Buddy
C. Demetrescu, M. Thorup. Oracles for distances avoiding a link-failure SODA 2002	Gjini Gabriel	Peter Widmayer	Rüegge Sandro Guido
M. B. T. Knudsen. Linear Hashing Is Awesome FOCS 2016	Kaufmann Jean Martin Charles	Przemysław Uznański	Li Gengyan
M. Thorup, U. Zwick. Approximate Distance Oracles STOC 2001	Christian Fania	Stefano Leucci	Gjini Gabriel
Y. Peres, D. Sotnikov, B. Sudakov, U. Zwick. All-Pairs Shortest Paths in O(n2) Time with High Probability FOCS 2010	Li Er Lu Lawrence	Przemysław Uznański	Dominik Häner
D. R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-out algorithm SODA 1993	Engel Lowis Anton	Stefano Leucci	Gessler Fabian Dieter
T. D. Hansen, H. Kaplan, R. E. Tarjan, U. Zwick. Hollow Heaps ICALP 2015	Peter Emanuel Viktor	Peter Widmayer	Rimle Philipp