General Information

---

Project Description

Our project aims to find a (randomized) \( 1 \) pass \( \tilde{O}(n) \) space streaming algorithm for \( \Delta \) coloring of a graph. Possible intermediate results are to find an \( O(1) \) pass algorithm, using sublinear (in the number of edges) space, or to find some lowerbounds.

---

Weekly Log

Week 1:

Usually this week would be unproductive because of travelling to a new country / administrative stuff; we do not have the luxury of this excuse, yet the week was unproductive all the same.
We did meet Prof Assadi once, and our main aim for now is to understand the \( \Delta+1 \) coloring algorithm from [ACK19].

Week 2:

We found a counterexample for a conjecture from last week; I don't fully understand the implications but I think it means that easy modifications to the existing algorithm will not suffice.
Sunday(7/6): I spent some time reading section 2 of [ACK19] and the proof of its Lemma 2.1 in [HSS16].

Week 3:

Tuesday(9/6): I walked through the proofs of Lemmas 3.1-3.3 of [ACK19]. My hope is to understand where exactly the proof breaks down if we just substitute \( \Delta \) for \( (\Delta + 1) \) everywhere, but so far I am unable to deal with all the details together. The third part of the proof (lemmas 3.4-3.5) seems even more technical, and I am scared off it for now.
I also started reading section 2 of [GHKM18], which has more structural results about \( \Delta-\) colorable graphs. For the most part this means I draw a lot of pictures to understand the casework-heavy proofs.

Week 4:

I have given up my brief attempt to update this log daily. Last week Prof Assadi asked us to focus on a very restricted version of \( \Delta-\)coloring: essentially to extend some partial coloring (which saved some colors) outside \( \epsilon-\)almost cliques to them. We worked out the details for this and wrote them up this week.

On Thursday Prof Assadi showed us sketches of the rest of the pieces; that is, how to get from the general \( \Delta-\)coloring problem to this reduced version -- our job is to convert the ideas into detailed proofs; if everything is correct we should have an \( o(n^2)-\)space algorithm for \( \Delta-\)coloring.

Week 5:

I filled in some of the details of the \( o(n^2)-\) space algorithm; so far things are looking good. We should be done with this by next week.
Also, the conference STOC was this week, obviously organised virtually because of the virus, which has nice side-effect of making attending it a no-brainer. I attended some talks and workshops, and have a large queue of papers to read now. There were also junior-senior "lunches", and I got to meet Prof Santosh Vempala, which was very cool.

Week 6:

We have filled in the details of the aforementioned algorithm to a satisfactory level. After setting some parameters we have a single-pass streaming algorithm with space usage \( \tilde{O}(n^{1 + \sqrt{2}/2}) \subset O(n^{1.70711}) \).
We believe it is possible to do better; the plan for the coming week (month?) is to explore some ideas for improving the algorithm; for example, it may be possible to avoid saving colors on sparse vertices as described above.

---

Presentations

• First Presentation
• Final Presentation

---