## Theory Lunch: Jukka Suomela on Distributed Computing | |

I really recommend the theory lunch this week. I think all of you can follow the talk easily and Jukka usually gives great talks. It might give lots of new ideas for your Master project. See the data below: Speaker: Jukka Suomela, Aalto University Time: Wednesday 22th of January, 12:30; food starts at 12:15. Location: Taub 201 Title: Foundations of Distributed Computing in the 2020s Abstract: In this talk I will review some major advances in the theory of distributed computing in the past decade and discuss key research challenges for the 2020s, with the main focus on distributed graph algorithms. I will present promising new approaches for doing research in the field, and I will also highlight examples of seemingly elementary questions that are still beyond the reach of our current techniques. |

פורסם ב- 19/1/2020, 12:06:41 Created on 19/1/2020, 12:06:41 Создано 19/1/2020, 12:06:41 تم النشر ب- 19/1/2020, 12:06:41 |

## Project Deadline 15th March | |

Hello all, as we discussed in the lecture (two weeks ago?) the project is due on 15th of March. But remember, I don't expect you to do strong modifications of the existing results. It is more about whether you can express the results, state of the art and technique used in your own words. See you on Thursday for the fast network decomposition algorithm, Yannic |

פורסם ב- 13/1/2020, 15:46:36 Created on 13/1/2020, 15:46:36 Создано 13/1/2020, 15:46:36 تم النشر ب- 13/1/2020, 15:46:36 |

## Lecture Today | |

A quick reminder: There will be a lecture today (5th of January) at 4.30 p.m. in Taub 8. |

פורסם ב- 5/1/2020, 14:10:43 Created on 5/1/2020, 14:10:43 Создано 5/1/2020, 14:10:43 تم النشر ب- 5/1/2020, 14:10:43 |

## Lecture on 5/01/2019 | |

The next lecture will be on 5th of January at 4.30 p.m. in Taub. We will cover a simple randomized graph coloring algorithm but much more importantly learn about the shattering technique which has been essential for almost all randomized algorithms in the area in the last 8 years, regardless of which distributed local graph problem has been solved. |

פורסם ב- 22/12/2019, 20:02:12 Created on 22/12/2019, 20:02:12 Создано 22/12/2019, 20:02:12 تم النشر ب- 22/12/2019, 20:02:12 |

## Tentative Remaining Schedule | |

The remaining lectures and a tentative schedule are as follows: 22/12: Network decompositions, ruling sets & MIS 05/01: Randomized coloring and the shattering technique 09/01: Randomized vs. deterministic algorithms: The SLOCAL story 16/01: The new network decomposition 23/01: Invited Speakers: The speedup lower bound technique and its applications |

פורסם ב- 15/12/2019, 21:56:35 Created on 15/12/2019, 21:56:35 Создано 15/12/2019, 21:56:35 تم النشر ب- 15/12/2019, 21:56:35 |

## Papers for Projects | |

Below are a few sample papers that you could take for the project but you are also welcome to take other papers. In either way you should contact me and tell me which paper you chose (first come first served). If you have questions about one of the papers or some other paper please ask me. In the project you're required do the following: 1. Read and understand the paper. Do not hesitate to approach me with questions. 2. Get familiar with the most important related work and the state of the start on the question. 3. Study a new question that is related to the paper. This is the creative part of the project. You are expected to say something interesting that relates to the paper that is not known. It is now late in the semester and I strictly emphasize to not overdue it. You are not supposed to spend an infinite amount of time on this! Examples for directions to look into are: What can be said if we remove an assumption about the model, e.g., knowledge of parameters? What can be said if we add an assumption about the model? What can be said if we restrict the family of graphs that are addressed? What can be said if we slightly relax the requirements of the problem? What can be said if we slightly strengthen the requirements of the problem? You are not expected to strictly improve upon the results of the paper, although this would be great and may even result in a publication. What you are expected to do is to ASK interesting question,and try to answer it. If you have a good question but cannot come up with an answer, then you can describe the directions you tried and the ways in which they were hard. Having good and meaningful questions here will also count. 4. Write a report on the paper using LaTeX (English language) and your own words. The report should describe the paper you read, the related work and state-of-the-art, and the new question you studied and its results. As a guideline I suggest at most 3 pages to describe the paper and related work, plus additional pages as you need them for the creative part. Fischer -Improved Deterministic Distributed matching via rounding https://arxiv.org/abs/1703.00900 Summary: Computing Maximal Matchings. Very nice paper. Korman, Sereni, Viennot - Toward More Localized Local Algorithms, Removing Assumotions Concerning Global Knowledge https://arxiv.org/abs/1512.03306 Summary: Which parameters (n, Delta) do you need to know to execute an algorithm? How can you remove these knowledge assumptions? Barenboim, Elkin - Deterministic Distributed Vertex Coloring in Polylogarithmic Time https://arxiv.org/abs/1003.1608 Summary: Computing Delta^(1+eps) coloring in O(log n * log Delta) time. Arbdefective Colorings! Kuhn - Faster Deterministic Distributed Coloring Through Recursive List Coloring https://arxiv.org/abs/1907.03797 Summary: Extends the paper above to lists. Only summarize the edge coloring part. New, state of the art for edge coloring! Chechik, Mukhtar - Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model https://arxiv.org/abs/1804.00137 Summary: Coloring planar graphs with 4, 5 or 6 colors. Schneider Elkin Wattenhofer - Symmetry Breaking Depending on the Chromatic Number or the Neighborhood Growth https://www.cs.bgu.ac.il/~elkinm/schneider.pdf Summary: Ruling sets and other things. A bit messy but not difficult Algorithms are correct, proofs... Barenboim - On the Locality of some NP Complete Problems https://arxiv.org/abs/1204.6675 Summary: Non standard paper that tries to color with f(n)*chi(G) colors for a pretty large f. Even, Medina, Ron - Best of Two Local Models, Centralized local and distributed local algorithms https://arxiv.org/abs/1402.3796 Summary: Different model where you pay for the volume and not the radius. Cute result. Randomized (papers are interesting but might be a bit technical): Pettie, Su -Distributed coloring algorithms for triangle-free Graphs Harris, Schneider, Su - Distributed Delta plus one Coloring in Sublogarithmic Rounds Chang, Li, Pettie - An Optimal Delta+1 Coloring Algorithm Approach me ASAP if you have any questions. |

פורסם ב- 15/12/2019, 21:40:40 Created on 15/12/2019, 21:40:40 Создано 15/12/2019, 21:40:40 تم النشر ب- 15/12/2019, 21:40:40 |

## Lectures from 19/12 and 2/1 moved to 22/12 and 5/1 | |

The lecture on 19th of December will be moved to Sunday the 22/12 according to the Technion schedule (it's Technion day on the 19th). Further the lecture on the 2nd of January will be moved to Sunday the 5th of January due to the Tel Aviv Theory festival. All lectures will be in Taub 8 |

פורסם ב- 12/12/2019, 13:08:01 Created on 12/12/2019, 13:08:01 Создано 12/12/2019, 13:08:01 تم النشر ب- 12/12/2019, 13:08:01 |

## Lecture Note Template | |

A template for "composing the lecture notes" can be found under "syllabus". Please contact me via email or personally if you encounter any problems or have suggestions for improvement. I hope you can all unpack the file :-) |

עדכון אחרון ב- 25/11/2019, 21:58:29 Last updated on 25/11/2019, 21:58:29 Последняя модификация 25/11/2019, 21:58:29 تمت الحتلنة الأخيرة ب- 25/11/2019, 21:58:29 |

## No Lecture Tomorrow | |

Just a reminder that there will be no lecture tomorrow on the 24th of October. We will start next week on the 31st of October. I am looking forward to the class. |

פורסם ב- 23/10/2019, 17:25:29 Created on 23/10/2019, 17:25:29 Создано 23/10/2019, 17:25:29 تم النشر ب- 23/10/2019, 17:25:29 |

## Template for Writing Lecture Notes | |

There will be a Template for Writing Lecture Notes. As material for the first three lectures can be found in lectures given by various professors around the world we will only start the "composing lecture notes for grading" after the first three lectures. This way you don't even get a chance to copy from previous lecture notes. |

פורסם ב- 6/10/2019, 10:04:09 Created on 6/10/2019, 10:04:09 Создано 6/10/2019, 10:04:09 تم النشر ب- 6/10/2019, 10:04:09 |

## Research Papers for Projects will be published in November | |

Possible research papers for the assignment will be published in November once we see how many students are attending the course and what students are interested in (there are many related research papers for the project to various related topics and I am sure we can find one that suits every student's interest!) Of course you can also suggest a paper (if it fits the course to some extend) that you want to study in the project. |

פורסם ב- 6/10/2019, 10:02:16 Created on 6/10/2019, 10:02:16 Создано 6/10/2019, 10:02:16 تم النشر ب- 6/10/2019, 10:02:16 |

## NO lecture in first week | |

There will be NO lecture on the first Thursday of the semester, that is, the course will start on Thursday, the 31st of October. |

פורסם ב- 6/10/2019, 10:00:37 Created on 6/10/2019, 10:00:37 Создано 6/10/2019, 10:00:37 تم النشر ب- 6/10/2019, 10:00:37 |