An optimal space lower bound for approximating MAX-CUT

DOI10.1145/3313276.3316364MaRDI QIDQ5212769zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Dmitry Krachun

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.10879

zbMATH Keywords

Fourier analysisMAX-CUTstreaming lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(logn)$ space, namely, count the number of edges and output half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed $epsilon>0$, if one allows $ildeO(n)$ space, a $(1+epsilon)$-approximate solution to the MAX-CUT value can be obtained by storing an $ildeO(n)$-size sparsifier that essentially preserves MAX-CUT value. Our main result is that any (randomized) single pass streaming algorithm that breaks the $2$-approximation barrier requires $Omega(n)$-space, thus resolving the space complexity of any non-trivial approximations of the MAX-CUT value to within polylogarithmic factors in the single pass streaming model. We achieve the result by presenting a tight analysis of the Implicit Hidden Partition Problem introduced by Kapralov et al.[SODA'17] for an arbitrarily large number of players. In this problem a number of players receive random matchings of $Omega(n)$ size together with random bits on the edges, and their task is to determine whether the bits correspond to parities of some hidden bipartition, or are just uniformly random. Unlike all previous Fourier analytic communication lower bounds, our analysis does not directly use bounds on the $el{l}_2$ norm of Fourier coefficients of a typical message at any given weight level that follow from hypercontractivity. Instead, we use the fact that graphs received by players are sparse (matchings) to obtain strong upper bounds on the $el{l}_1$ norm of the Fourier coefficients of the messages of individual players, and then argue, using the convolution theorem, that similar strong bounds on the $el{l}_1$ norm are essentially preserved once messages of different players are combined.

Recommendations

• (1 + (1))-approximation to MAX-CUT requires linear space
• Streaming Lower Bounds for Approximating MAX-CUT
• Sketching cuts in graphs and hypergraphs
• Sublinear algorithms for MAXCUT and correlation clustering
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph

Cited in

(13)

• Sketching cuts in graphs and hypergraphs
• (1 + (1))-approximation to MAX-CUT requires linear space
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Sublinear algorithms for MAXCUT and correlation clustering
• Optimal Bounds for the k -cut Problem
• Streaming Lower Bounds for Approximating MAX-CUT
• scientific article; zbMATH DE number 7650072 (Why is no real title available?)
• Revisiting maximum satisfiability and related problems in data streams
• Revisiting maximum satisfiability and related problems in data streams
• Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
• Streaming approximation resistance of every ordering CSP
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Sketching approximability of all finite CSPs

This page was built for publication: An optimal space lower bound for approximating MAX-CUT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212769)