## 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(log n) 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 ε > 0, if one allows Õ (n) space, a (1+ε)-approximate solution to the MAX-CUT value can be obtained by storing an Õ (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 Ω(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 Ω(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 ℓ_{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 ℓ_{1} norm of the Fourier coefficients of the messages of individual players using their special structure, and then argue, using the convolution theorem, that similar strong bounds on the ℓ_{1} norm are essentially preserved (up to an exponential loss in the number of players) once messages of different players are combined. We feel that our main technique is likely of independent interest.

Original language | English (US) |
---|---|

Title of host publication | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Moses Charikar, Edith Cohen |

Publisher | Association for Computing Machinery |

Pages | 277-288 |

Number of pages | 12 |

ISBN (Electronic) | 9781450367059 |

DOIs | |

State | Published - Jun 23 2019 |

Externally published | Yes |

Event | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States Duration: Jun 23 2019 → Jun 26 2019 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 |
---|---|

Country/Territory | United States |

City | Phoenix |

Period | 6/23/19 → 6/26/19 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Fourier analysis
- MAX-CUT
- Streaming lower bounds