An optimal space lower bound for approximating MAX-CUT

DOI10.1145/3313276.3316364zbMath1433.68621arXiv1811.10879OpenAlexW2963692174MaRDI QIDQ5212769

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

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

Related Items (3)

Revisiting maximum satisfiability and related problems in data streams ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Unnamed Item

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