## Abstract

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a (1+?)-approximation requires either n?(1) space or ?(1/?) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller o(log(1/?)) passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a p-pass s-space streaming algorithm can only solve a decision problem with advantage ?> 0 over random guessing, then it cannot solve XOR of ? independent copies of the problem with advantage much better than ?. This result can be of independent interest and useful for other streaming lower bounds as well.

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

Title of host publication | STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Samir Khuller, Virginia Vassilevska Williams |

Publisher | Association for Computing Machinery |

Pages | 612-625 |

Number of pages | 14 |

ISBN (Electronic) | 9781450380539 |

DOIs | |

State | Published - Jun 15 2021 |

Event | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: Jun 21 2021 → Jun 25 2021 |

### Publication series

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

ISSN (Print) | 0737-8017 |

### Conference

Conference | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 |
---|---|

Country/Territory | Italy |

City | Virtual, Online |

Period | 6/21/21 → 6/25/21 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Communication Complexity
- Graph Streaming
- MAXCUT
- Pointer Chasing
- Property Testing
- XOR lemma