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.13.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.43.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 caseworkheavy 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 sideeffect of making attending it a
nobrainer. I attended some talks and workshops, and have a large queue of
papers to read now. There were also juniorsenior "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 singlepass
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
Resources
 [ACK19]: Sublinear Algorithms for \( (\Delta + 1)\) coloring;
Sepehr Assadi, Yu Chen, Sanjeev Khanna
[arXiv]
 [HSS16]: Distributed \( (\Delta + 1)\) coloring in sublogarithmic rounds;
David Harris, Johannes Schneider, HsinHao Su
[arXiv]
 [GHKM18]: Improved Distributed \( (\Delta)\) Coloring;
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus
[arXiv]