DIMACS REU 2020

Student: | Andrew Chen |
---|---|

School: | Carnegie Mellon University |

E-mail: | andrewc3@andrew.cmu.edu |

Mentor: | Sepehr Assadi |

Project: | Decentralized Graph Coloring |

To determine whether or not there exists a *deterministic* single pass dynamic streaming algorithm for the 2Δ-coloring problem.

** Tuesday (5/26)**: Orientation day, met other students in the program.

** Wednesday (5/27)**: Attended Parker's workshop on creating my own website, began adding images and formatting my sebsite.

** Thursday (5/28)**: Met my advisor Sepehr Assadi for the first time. We introduced ourselves, discussed some background knowledge on graphs and the streaming model of computation, and then worked through most of the details of a randomized 2Δ-coloring algorithm. I was assigned a reading on the streaming model and to complete and write up the proof of the 2Δ algorithm as an exercise.

** Friday (5/29)**: Worked on the 2Δ algorithm; completed writing up everything except for the O(nlog

** Saturday (5/30)**: Starting creating a preliminary presentation on my project for Monday. Learned how to use the Beamer package in LaTeX to write my presentation in. Also completed the aforementioned O(nlog

** Sunday (5/31)**: Finished creating and preparing for my presentation; also read through the graph streaming model survey.

** Monday (6/1)**: Met with Professor Assadi early in the morning to review and make last minute changes to my slides. Also received a new reading on communication complexity for our upcoming Thursday meeting. I then presented during the first round of presentations. For the rest of the day I finished up some alternative solutions to the 2Δ algorithm which used a Chernoff bound rather than Chebyshev's inequality.

** Tuesday (6/2)**: Attended the second round of presentations. Read Lecture 1 of the communication complexity notes. Some more website tweaking as well.

** Wednesday (6/3)**: Realized a flaw in the alternate solution I was attempting to write up, which I tried and failed to fix.

** Thursday (6/4)**: Finished working through the alternate solution from Wednesday.

** Friday (6/5)**: Researched some alternate methods of tackling the problem. I found a couple of papers that achieved other types of colorings; for example, I read through a paper on κ colorings, where κ(G) is the degeneracy of a graph. Although their approach resulted in a probabilistic algorithm, the general approach might be adaptable to the O(Δ) coloring that we are trying to find.

** Monday (6/8)**: Attended the data science boot camp in the morning. Met with Professor Assadi in the afternoon and discussed a new approach to a weaker O(Δ

** Tuesday (6/9)**: Focused on learning McDiarmid's inequality and clarifying with Professor Assadi how exactly it should be applied in this context.

** Wednesday (6/10)**: Worked out most of the details of the algorithm that we discussed during our meeting on Monday. It remains to investigate whether or not the lower bound on the desired probability of aborting actually holds.

** Thursday (6/11)**: The last remaining problem arises from the fact that our edge counting function is O(Δ)-Lipschitz as opposed to O(1)-Lipschitz, which yields an upper bound on the probability of exp(-Θ(n/Δ

** Friday (6/12)**: Found a highly technical paper that seems to prove a generalized version of McDiarmid, but it was too dense for me to extract anything useful. On a high level, however, it seems that the results they prove won't be applicable here. Instead of pursuing it further, I went over our original O(Δ

** Monday (6/15)**: Professor Assadi and I discussed the approach we took last week, and managed to show that our original claim was actually false; indeed, the counterexample I found on Thursday taken with the case where Δ = Θ(n) yields a large (>>Θ(n)) number of edges in just a single partition with an uncomfortably high probability (>>2

** Tuesday (6/16)**: I worked out the details for the O(Δ

** Wednesday (6/17)**: The Δ

** Thursday (6/18)**: Since there does not seem to be any way to continue with this probabilistic approach, I continued to look for other research done in the area. I came across Nathan Linial's 1992 paper on distributed graph coloring algorithms. Although he worked in the LOCAL model, I spent some time looking at his paper in the hope that the combinatorial results (of Erdös, Frankl, and Füredi) that he used might be applicable to the streaming model.

** Friday (6/19)**: Continued perusing various related papers.

** Monday (6/22)**: The STOC conference began this week, and I spent most of this day attending the various talks and workshops. Due to STOC, Professor Assadi and I postponed our meeting to next week.

** Tuesday (6/23)**: I continued to attend the STOC talks.

** Wednesday (6/24)**: Although unrelated to my research, I was very interested in the sunflower lemma paper presented in Session 5, since the results are of a more mathematical/combinatorial nature.

** Thursday (6/25)**:

** Friday (6/26)**:

** Monday (6/29)**: During our meeting, Professor Assadi presented a new approach for a multi-pass (O(logΔ)-pass) algorithm which produces an O(Δ

** Tuesday (6/30)**: Attended the Rebecca Wright workshop on privacy in the digital world. I then spent the rest of the day familiarizing myself with the algorithm that Professor Assadi and I discussed on Monday. The nature of the algorithm makes it unclear how to reduce the number of passes, so I will primarily focus on reducing the number of colors used.

** Wednesday (7/1)**: It is intuitively reasonable that the maximum degrees of each cluster is something much smaller than Δ; as such, I focused my efforts today on trying to bound the maximum degree of each cluster. A probabilistic argument suggests that the maximum degrees should be constant; if I could show this then I would immediately have an O(Δ)-coloring algorithm, which is asymptotically tight.

** Thursday (7/2)**: Attended the scientific writing workshop. Continued trying to bound the maximum degree of the clusters.

** Friday (7/3)**: Off for Fourth of July.

** Monday (7/6)**:

** Tuesday (7/7)**:

** Wednesday (7/8)**:

** Thursday (7/9)**:

** Friday (7/10)**:

- Professor Assadi's paper on the existence of a randomized single pass dynamic streaming (Δ+1)-coloring algorithm
- Lecture notes on communication complexity
- A survey on the graph streaming model

- DIMACS for hosting this program
- The NSF for supporting my research through NSF grant CCF-1852215