# Reading Group Algorithms

## Seminar

## Basic Information

Given by: | Kurt Mehlhorn, Bhaskar Ray Chaudhury |
---|---|

Time: | (Wednesday, 4:15 PM) |

Room: | E1.4 024 |

First Meeting: | April, 10th |

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 **tba** (around 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 Bhaskar. Please make sure that you read the section on prerequisites above before you register.

## News

- There are no news yet.

## Schedule

Date | Speaker | Topic | Reference |
---|---|---|---|

Apr, 10 | Bhaskar | Introduction to the Reading Group
| [Apr10] |

Approximating Maximin Share Allocations | |||

Apr, 17 | Kurt | The Query Complexity of a Permutation-Based Variant of Mastermind | [Apr17] |

Apr, 24 | Bhaskar | The Geometry of Binary Search Trees | [Apr24] |

May, 1 | <labor day> | ||

May, 8 | André | Approximating (k,l)-center clustering for curves | [May8] |

May, 15 | Alkmini | Universal Traveling Salesman Problem | [May15] |

May, 22 | Corinna | Local Computation: Lower and Upper Bounds | [May22] |

May, 29 | Jannis | Approximating LCS in Linear Time: Beating the sqrt(n) Barrier | [May29] |

Jun, 5 | Sebastian | Almost Envy-Freeness with General Valuations | [Jun5] |

Jun, 12 | Elizaveta | Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line | [Jun12] |

Jun, 19 | Pranabendu | Lower Bounds for Multiplication via Network Coding | [Jun19] |

Jun, 26 | Daniel | Sparsest Cut on Bounded Treewidth Graphs | [Jun26] |

Jul, 3 | Alejandro | A note on Max K-Vertex Cover: Faster FPTAS, Smaller Approximate Kernel and Improved Approximation | [Jul3] |

Jul, 10 | Virab | An Illuminating Algorithm for the Light Bulb Problem | [Jul10] |

Jul, 17 | Lennart | Separating Monotone VP and VNP | [Jul17] |

## Papers

List of papers available for students.

## References

Paper Title / Abstract of Talk | Authors | |

[Apr10] | Approximating Maximin Share Allocations | Jugal Garg, Peter McGlaughlin, Setareh Taki |

[Apr17] | Query Complexity of a Permutation-Based Variant of Mastermind | Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn |

[Apr24] | The Geometry of Binary Search Trees | Erik D, Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu |

[May8] | Approximating (k, ℓ)-center clustering for curves | Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, Martijn Struijs |

[May15] | Spacefilling curves and the planar travelling salesman problem | Loren K. Platzman, John J. Bartholdi |

[May22] | Local Computation: Lower and Upper Bounds | Fabian Kuhn, Thomas Moscibroda, Roger Wattenhoffer |

[May29] | Approximating LCS in Linear Time: beating the sqrt(n) Barrier | MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiourui Sun |

[Jun5] | Almost Envy-Freeness with General Valuations | Benjamin Plaut, Tim Roughgarden |

[Jun12] | Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line | Sharath Raghavendra |

[Jun19] | Lower Bounds for Multiplication via Network Coding | Peyman Afshani, Casper Freksen, Lior Kamma, Kasper Green Larsen |

[Jun26] | Sparsest Cut on Bounded Treewidth Graphs | Anupam Gupta, Kunal Talwar, David Witmer |

[Jul3] | A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation | Pasin Manurangsi |

[Jul10] | An Illuminating Algorithm for the Light Bulb Problem | Josh Alman |

[Jul17] | Separating Monotone VP and VNP | Amir Yehudayoff |