| Name: | Liubov (Luba) Samborska |
|---|---|
| Email: | liubov.samborska@yale.edu |
| Home Institution: | Yale University |
| Project: | Two-way Communication Complexity of Max-Cut |
| Mentor: | Professor Sepehr Assadi |
Please click here to view my final presentation slides.
We decided on a problem that I will be working on this summer, and I did some background reading from this course, taught by Prof. Assadi in Fall 2021. I worked on a presentation that would introduce my project to the rest of the REU participants next week.
I learned about the Ω(m) communication complexity lower bound for Set Disjointness - in this problem, Alice and Bob have A, B ⊆ [m] respectively, and either A ∩ B = ∅ or A ∩ B = {i} for some i ∊ [m]. I also learned about the Ω(n) communication complexity lower bound for Graph Connectivity, where n is the number of vertices in the graph (this lower bound follows from a reduction from Set Disjointness). Later in the week, I started reading through common reductions showing NP-Completeness of Max-Cut.
We continued exploring the common reductions showing NP-Completeness of Max-Cut, in order to see if they remain useful for our purposes in the communication complexity setting. This included reductions from Maximum Independent Set, Partition, and NAE 3-SAT (the latter two reducing to weighted Max-Cut). As a pit stop, I learned about the Ω(n^2) communication complexity lower bound for Max Independent Set (and the related Max Clique problem) - which also follows from a reduction from Set Disjointness.
We thought about and proved an Ω(n^2) communication complexity lower bound for the 3-Coloring problem through a reduction from Disjointness, related to the reduction in [1]. We believed this would be useful in proving an Ω(n^2) communication complexity lower bound for Max-Cut, through a chain of reductions from 3-Coloring to (weighted) Max-Cut. We took a detailed look at the techniques used in [2].
We found an issue in one of the reductions in our chain (namely the introduction of too many variables in the SAT to NAE 3-SAT reduction) and discussed our options for fixing it. We further explored some of the mentioned options, and settled on one that seemed to have the most promise. I also worked on writing up the proof of the Ω(n^2) lower bound for the 3-Coloring problem.
We confirmed that our designed direct reduction from 3-Coloring to NAE 3-SAT (i.e. a fix to the issue mentioned in the previous week) is correct and accomplishes our lower bound goal. We finished the week off with a chain of reductions that establishes an Ω(n^2) lower bound for two-way communication complexity of (Weighted) Max Cut.
We thought about possible reductions from Weighted Max Cut to unweighted Max Cut (i.e. all edge weights equal to 1), with the goal of establishing a communication complexity lower bound stronger than Ω(n). We looked at some reductions from weighted to unweighted Max Cut, including the one presented in [3]. None of the encountered general-case reductions were directly useful for accomplishing the lowerbound goal, so we started thinking about an original reduction.
We talked about an original reduction from weighted to unweighted Max-Cut which doesn't quite work, since it neccesitates that we deal with non-integer numbers of vertices. We talked about ideas for fixing this and I worked on my final presentation, which took place on Thursday, July 21. (Update: we have since fixed our weighted to unweighted Max-Cut reduction, establishing an Ω(n^4/3) lower bound for unweighted Max-Cut.)
I attended the 2022 Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms, and Applications. I also worked on my end-of-the-program paper.