- Two-way Communication Complexity of Weighted Maximum Cut
- Project Year:
2022
- REU Student (s):
Liubov Samborska | Yale University CT
- Student 1 Institution:
Yale University
- Project Mentor:
Sepehr Assadi
- Project Mentor Area:
Computer Science
- Project Abstract:
In this project, we consider the well-known Weighted Max-Cut problem in the context of two-party communication. We establish a two-way randomized communication complexity lower bound of Ω(n^2) for Weighted Max-Cut on graphs with n vertices, which differs from the trivial upper bound by only a logarithmic factor. To establish the desired lower bound, we construct a chain of communication reductions: Disjointness to 3-Coloring, 3-Coloring to NAE 3-SAT, and finally NAE 3-SAT to Weighted Max-Cut. The reductions we present are non-arbitrary, as the size of constructed instances and the amount of communication used in the reduction impact the strength of the resulting lower bound. We thus apply reductions in a white-box manner, establishing the communication complexity lower bound of Ω(n^2) for Weighted Max-Cut and additional lower bounds for the intermediate problems of 3-Coloring and NAE 3-SAT in the communication reduction chain.
