Impossibility Results for Local Algorithms

Impossibility Results for Local Algorithms

In algorithmic research, many works focus on obtaining faster, simpler, or otherwise improved algorithms. But how do we know when to stop searching for better algorithms, how do we know that we have exhausted all possibilities for improvement and reached the optimum?

In this seminar, we will take a look into the wonderful world of impossibility results, i.e., results that tell us that obtaining a certain algorithmic objective is provably impossible. While, in general, impossibility results come in many different flavors, the impossibility results that we will study are, to a large extent, runtime lower bounds that rule out the existence of algorithms (for a fixed problem or problem class) that are faster than a certain runtime threshold. Moreover, our focus will be on impossibility results for distributed (and related) algorithms for graph problems. More specifically, the computational model that we will most frequently encounter in this seminar will be the LOCAL model of distributed computation. Note that this is a theory seminar, i.e., we will focus on lower bound proofs, algorithm analysis, and the like.

In this seminar, each student has to present one or two assigned paper(s). Each presentation is followed by a discussion lead by the presenter. Besides presentation and participation in the discussion, the grade will depend on written deliverables.

The required language for the presentations is English.
If you are interested in this seminar, please register your interest in the seminar assignment system.

 

Date, Time, Location

The default weekly slot for the seminar will be Tuesday, 16:00 - 18:00. The location for the seminar is building E9 1 (CISPA), room 0.05. The kick-off meeting will take place on Nov 5, 16:00 - 18:00.

 

Prerequisites

There are no formal prerequisites for this seminar, but a general interest in graph theory and designing/analyzing algorithms as well as a basic understanding of probabilities and algorithmic analysis (e.g., O-notation) will be helpful.