Reading Group Algorithms

Seminar

Basic Information

Given by:Kurt Mehlhorn, Daniel Vaz
Time:Wednesday, 4:15 PM
Room:022 (MPI-INF)
First Meeting:April, 11th
Credits:7 credit points
Prerequisites:You should bring a solid background in algorithms and data structures. This is an advanced seminar. The papers are challenging and a proper preparation of your talk will require some effort. Thus, you should bring a great passion for theoretical computer science. The target audience of this reading group are master students, PhD students, as well as postdocs.

Description

We will read (more or less) recent papers in theoretical computer science. The paper may be less recent if there is interesting follow-up work. In each session we have a regular presentation (40-60 minutes + discussion) of one paper. The reading group is open for all interested students and postdocs. Students aiming to get credit points must give a regular talk and write a short summary about the paper.

You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a short summary (about 5 pages). The summary should be handed in within the first two weeks after the end of the semester, more precisely until August, 15th. You will receive comments and can improve your summary based on our comments. The presentation needs to be discussed with us at least one week before your scheduled talk in the reading group (you are supposed to give a practice talk to your supervisor).

The reading group counts as a seminar in your study program. You can register by sending an e-mail to Daniel. Please make sure that you read the section on prerequisites above before you register.

News

  • There will be no reading group today, April 25th.

Schedule

DateSpeakerTopicReference
Apr, 11DanielIntroduction to the Reading Group 
 BhaskarOptimal Polyline Simplification under Hausdorff and Frechet distance[Apr11]
Apr, 18DanielMinimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs[Apr18]
Apr, 25 <cancelled> 
May, 2DavisDeciding k-colorability of P5-free graphs in polynomial time[May02]
May, 9NitinArithmetic Circuits : A chasm at depth four[May09]
May, 16AndreasSparse Kneser graphs are Hamiltonian[May16]
May, 23AndréA faster algorithm for the discrete Fréchet distance under translation[May23]
May, 30EunjinDynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier[May30]
Jun, 6BenA Distributed Algorithm for Spanning Trees[Jun06]
Jun, 13Pavel

<cancelled>

[Jun13]
Jun, 20PavelApproximating Maximum Clique[Jun20]
Jun, 27Andreas SchmidGeneralized comparison trees for point-location problems[Jun27]
Jul, 4Anna KrasilnikovaComplex brain networks: graph theoretical analysis of structural and functional systems[Jul04]
Jul, 11MaxA Friendly Smoothed Analysis of the Simplex Method[Jul11]
Jul, 18Emanuele NataleTBA[Jul18]
Jul, 25  [Jul25]

References

 Paper Title / Abstract of TalkAuthors
[Apr11]Optimal Polyline Simplification under Hausdorff and Frechet distanceMarc van Kreveld, Maarten Löffler, Lionov Wiratma
[Apr18]Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs

André Berger, Michelangelo Grigni

[May02]Deciding k-colorability of P5-free graphs in polynomial time

Chính T. Hoàng, Marcin Kamiński, Vadim Lozin, Joe Sawada, Xiao Shu

[May09]

Arithmetic Circuits : A chasm at depth four

Manindra Agrawal, V Vinay

 Arithmetic Circuits: The Chasm at Depth Four Gets Wider

Pascal Koiran

 Improved Bounds for Reduction to Depth 4 and Depth 3

Sébastien Tavenas

[May16]Sparse Kneser graphs are Hamiltonian

Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak

[May23]A faster algorithm for the discrete Fréchet distance under translation

Rinat Ben Avraham, Haim Kaplan, Micha Sharir

[May30]Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Omer Gold, Micha Sharir

[Jun06]A Distributed Algorithm for Minimum-Weight Spanning Trees

Robert G. Gallager, Pierre A. Humblet, Philip M. Spira

[Jun13][cancelled] 
[Jun20]  
[Jun27]Generalized comparison trees for point-location problems

Daniel M Kane, Shachar Lovett, Shay Moran

[Jul4]Complex brain networks: graph theoretical analysis of structural and functional systems

Ed Bullmore, Olaf Sporns

[Jul11]A Friendly Smoothed Analysis of the Simplex Method

Daniel Dadush, Sophie Huiberts

[Jul18]  
[Jul25]