Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Research Seminar (Winter Term 2020)

<previous seminar | next seminar>

COVID-19 and virtual seminars

Due to the current situation we are not hosting seminars at the HPI anymore. Instead, we host virtual seminars via zoom. If you want to join the seminar on short notice or if you do not want to subscribe to the mailing list, please send an email to ralf.rothenberger(at)hpi.de.

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich or to Ralf Rothenberger.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

DateRoom SpeakerTitle
13.10. 13:00virtualMartin Krejca

Drift theory is a collection of theorems that bound the expected stopping time of time-discrete random processes over the reals that have a consistent bias – the drift – in decreasing in expectation in each step. The beauty of drift theory stems from translating a bound for the drift immediately into a bound for the expected stopping time. In other words, local information about the one-step change of the process is turned into global information about the behavior of the entire process. However, a downside of drift theory is that the application of a drift theorem is usually preceded by defining a useful potential function that transform the random process into one that has the desired drift. This step is not straightforward.

One problem in determining a useful potential function is that the transformed process needs to have drift in each step, that is, no detours into the wrong direction are allowed, even when they are deterministic. In this talk, we present the time-flexible drift theorem, a new drift theorem that does not have this limitation. It generalizes the most general drift theorem as well as similar approaches that bound the expected stopping time. The time-flexible drift theorem allows for time periods in the random process that do not show the desired drift. Such periods are handled separately and then incorporated into the final result.

This talk presents work in progress (that I came up with last week). In fact, I have no super cool application for this new theorem in mind. I stumbled upon it while thinking about something different. So I would be glad to get some feedback or ideas or start some new collaboration. As a feature, some parts of the talk are very formal (and assume a very formal background in probability theory), which should motivate you to have an in-depth discussion with me after the talk if you would like to learn more =D. Nonetheless, the talk also includes the mandatory (somewhat) colorful pictures with fancy animations and is aimed to convey the intuition of the math beneath.

20.10. 13:00virtualArdalan Khazraei
The cost-distance Steiner tree problem asks for a Steiner tree in a graph that minimizes the total cost plus a weighted sum of path delays from the root to the sinks. We present an improved approximation for the uniform cost-distance Steiner tree problem, where the delay of a path corresponds to the sum of edge costs along that path. Previous approaches deploy a bicriteria approximation algorithm for the length-bounded variant that does not take the actual delay weights into account. Our algorithm modifies a similar algorithm for the single-sink buy-at-bulk problem by Guha et al. [2009], allowing a better approximation factor for our problem. In contrast to the bicriteria algorithms it considers delay weights explicitly. Thereby, we achieve an approximation factor of (1+β), where β is the approximation factor for the Steiner tree problem. This improves the previously best known approximation factor for the uniform cost-distance Steiner tree problem from 2:87 to 2:39. This algorithm can be extended to the problem where the ratio of edge costs to edge delays throughout the graph is bounded from above and below. In particular, this shows that a previous inapproximability result (Chuzhoy et al. [2008]) requires large variations between edge delays and costs. Finally, we present an important application of our new algorithm in chip design. The cost-distance Steiner tree problem occurs as a Lagrangean subproblem when optimizing millions of Steiner trees with mutually depending path length bounds. We show how to quickly approximate a continuous relaxation of this problem with our new algorithm.
23.10. 13:00virtualGregor Lagodzinski

During the first half of this year I worked at SAP as an intern, to be precise, at the SAP Innovation Center Network location in Potsdam. The goal of this internship was to see, observe and take part of the world outside of academia. Needless to say, things did not go as planned and I got first-hand experience into how a big company like SAP handles a special situation like the COVID-19 pandemic. First and foremost, they will still work and so did I.

In this lightweight talk I will present my insights gained during the internship. This will incorporate a narrative about the process before the internship, a very rough insight in my tasks, and a first example of what a Zero-knowledge proof is. Finally, I will present my personal résumé and an outlook as to how it affected my near future.