Skip to main navigation Skip to search Skip to main content

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

  • Lijie Chen
  • , Gillat Kol
  • , Dmitry Paramonov
  • , Raghuvansh R. Saxena
  • , Zhao Song
  • , Huacheng Yu
    • University of California at Berkeley
    • Princeton University
    • Microsoft USA

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    10 Scopus citations

    Abstract

    We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, showing that they require linear space to guarantee a better-than-2 approximation [50, 52]. This result relies on a lower bound for the cycle-finding problem, showing that it is hard for a one-pass streaming algorithm to find a cycle in a union of matchings. The end-goal of our research is to prove a similar lower bound for multi-pass streaming algorithms that guarantee a better-than-2 approximation for Max-Cut, a highly challenging open problem. In this paper, we take a significant step in this direction, showing that even o(log n)-pass streaming algorithms need nΩ(1) space to solve the cycle-finding problem. Our proof is quite involved, dividing the cycles in the graph into “short” and “long” cycles, and using tailor-made lower bound techniques to handle each case.

    Original languageEnglish
    Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
    Pages878-924
    Number of pages47
    ISBN (Electronic)9781611977554
    StatePublished - 2023
    Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
    Duration: 22 Jan 2023 → 25 Jan 2023

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
    Volume2023-January

    Conference

    Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
    Country/TerritoryItaly
    CityFlorence
    Period22/01/23 → 25/01/23

    Fingerprint

    Dive into the research topics of 'Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut'. Together they form a unique fingerprint.

    Cite this