Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, December 08, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Christoph Grunau

Distributed Derandomization via Local Rounding

In this talk, I will present a general distributed derandomization method which allows to locally round fractional solutions of graph problems. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). Informally speaking, the method allows to efficiently derandomize randomized algorithms which only require pairwise independence. The method is used by the state-of-the art deterministic algorithms for problems such as maximal independent set or network decomposition, two of the most central problems in distributed computing. This is joint work with Salwa Faour, Mohsen Ghaffari, Fabian Kuhn and Václav Rozhoň.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login