License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.11
URN: urn:nbn:de:0030-drops-94156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9415/
Go to the corresponding LIPIcs Volume Portal

Eden, Talya ; Rosenbaum, Will

Lower Bounds for Approximating Graph Parameters via Communication Complexity

pdf-format:
LIPIcs-APPROX-RANDOM-2018-11.pdf (0.5 MB)

Abstract

In a celebrated work, Blais, Brody, and Matulef [Blais et al., 2012] developed a technique for proving property testing lower bounds via reductions from communication complexity. Their work focused on testing properties of functions, and yielded new lower bounds as well as simplified analyses of known lower bounds. Here, we take a further step in generalizing the methodology of [Blais et al., 2012] to analyze the query complexity of graph parameter estimation problems. In particular, our technique decouples the lower bound arguments from the representation of the graph, allowing it to work with any query type.
We illustrate our technique by providing new simpler proofs of previously known tight lower bounds for the query complexity of several graph problems: estimating the number of edges in a graph, sampling edges from an almost-uniform distribution, estimating the number of triangles (and more generally, r-cliques) in a graph, and estimating the moments of the degree distribution of a graph. We also prove new lower bounds for estimating the edge connectivity of a graph and estimating the number of instances of any fixed subgraph in a graph. We show that the lower bounds for estimating the number of triangles and edge connectivity also hold in a strictly stronger computational model that allows access to uniformly random edge samples.

BibTeX - Entry

@InProceedings{eden_et_al:LIPIcs:2018:9415,
  author =	{Talya Eden and Will Rosenbaum},
  title =	{{Lower Bounds for Approximating Graph Parameters via Communication Complexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9415},
  URN =		{urn:nbn:de:0030-drops-94156},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.11},
  annote =	{Keywords: sublinear graph parameter estimation, lower bounds, communication complexity}
}

Keywords: sublinear graph parameter estimation, lower bounds, communication complexity
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI