License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.91
URN: urn:nbn:de:0030-drops-156876
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15687/
Kapralov, Michael ;
Musipatla, Amulya ;
Tardos, Jakab ;
Woodruff, David P. ;
Zhou, Samson
Noisy Boolean Hidden Matching with Applications
Abstract
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et al. [STOC'07], has played an important role in lower bounds for graph problems in the streaming model (e.g., subgraph counting, maximum matching, MAX-CUT, Schatten p-norm approximation). The BHM problem typically leads to Ω(√n) space lower bounds for constant factor approximations, with the reductions generating graphs that consist of connected components of constant size. The related Boolean Hidden Hypermatching (BHH) problem provides Ω(n^{1-1/t}) lower bounds for 1+O(1/t) approximation, for integers t ≥ 2. The corresponding reductions produce graphs with connected components of diameter about t, and essentially show that long range exploration is hard in the streaming model with an adversarial order of updates.
In this paper we introduce a natural variant of the BHM problem, called noisy BHM (and its natural noisy BHH variant), that we use to obtain stronger than Ω(√n) lower bounds for approximating a number of the aforementioned problems in graph streams when the input graphs consist only of components of diameter bounded by a fixed constant.
We next introduce and study the graph classification problem, where the task is to test whether the input graph is isomorphic to a given graph. As a first step, we use the noisy BHM problem to show that the problem of classifying whether an underlying graph is isomorphic to a complete binary tree in insertion-only streams requires Ω(n) space, which seems challenging to show using either BHM or BHH.
BibTeX - Entry
@InProceedings{kapralov_et_al:LIPIcs.ITCS.2022.91,
author = {Kapralov, Michael and Musipatla, Amulya and Tardos, Jakab and Woodruff, David P. and Zhou, Samson},
title = {{Noisy Boolean Hidden Matching with Applications}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {91:1--91:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15687},
URN = {urn:nbn:de:0030-drops-156876},
doi = {10.4230/LIPIcs.ITCS.2022.91},
annote = {Keywords: Boolean Hidden Matching, Lower Bounds, Communication Complexity, Streaming Algorithms}
}
|
Keywords: |
|
Boolean Hidden Matching, Lower Bounds, Communication Complexity, Streaming Algorithms |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
