Project Description

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

Weekly Updates

Week 1 (5/26-5/31):

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²n) space bound on the number of retained edges. Also made the website look nice(r).

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²n) space bound.

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

Week 2 (6/1-6/7):

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.

Week 3 (6/8-6/14):

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(Δ²) algorithm, which is reliant on proving lower bounds on the probability that our randomized algorithm aborts. The focus of this week will be to learn McDiarmid's inequality and apply it to achieve the desired lower bound of exp(-Θ(n)), so that we can use typical derandomization techniques to achieve a deterministic algorithm.

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/Δ²)). Unfortunately, this bound is tight in the current context, since it can be achieved by having n/(Δ+1) disjoint copies of cliques of order (Δ+1). However, this is an extremely improbable event given that the vertex sampling occurs uniformly at random; maybe there exists a high probability version of McDiarmid's that we can apply here?

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(Δ²) algorithm looking for other ways to improve the probability.

Week 4 (6/15-6/21):

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^-Θ(n)). For this week, we will try to adapt our previous work for an even weaker O(Δ³) coloring algorithm. Once that is complete, we will investigate ways of reducing this dependency on Δ to something smaller like O(Δ²) or O(Δ^2.5) by leveraging McDiarmid in different ways.

Tuesday (6/16): I worked out the details for the O(Δ³) algorithm, which uses two passes, and wrote up the completed proof. I also investigated an idea proposed by Professor Assadi, defining an auxiliary function which only counts Δ^0.5 edges per vertex. The idea is to apply McDiarmid's to this auxiliary function (which is now O(Δ^0.5)-Lipschitz and achieves a better probabilistic bound) and show that the true number of retained edges is not much larger than this quantity. Unfortunately, the case of disjoint Δ+1 cliques demonstrates that this difference can be too large for this method to work.

Wednesday (6/17): The Δ^0.5 counting approach didn't work, I began looking into other methods of tackling the problem. One thing that I considered was to look at the degeneracy of the subgraphs, since it is well known that a graph with degeneracy κ can be κ+1 colored. Some research later, I was unable to find anything useful.

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.

Week 5 (6/22-6/28):

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):

Week 6 (6/29-7/5):

Monday (6/29): During our meeting, Professor Assadi presented a new approach for a multi-pass (O(logΔ)-pass) algorithm which produces an O(Δ²) coloring. In comparison to our previous best algorithm, this improves on the number of colors by a factor of Δ at the cost of logΔ more passes of the stream. The idea of this approach is to recursively partition vertices into O(Δ) clusters, in such a way that the number of edges which survives is Õ(n). Each cluster can be Δ-colored, yielding an O(Δ²) coloring. The goals of this week are to either improve the number of passes needed, or to improve the number of colors used.

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.

Week 7 (7/6-7/12):

Monday (7/6):

Tuesday (7/7):

Wednesday (7/8):

Thursday (7/9):

Friday (7/10):

Resources:

• 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

Acknowledgements:

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