2017/09/13 by Talya Eden, Eden, Talya, Will Rosenbaum +1 · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1709.04262
openalex publication_date 2017/09/13 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
In a celebrated work, Blais, Brody, and Matulef developed a technique for\nproving property testing lower bounds via reductions from communication\ncomplexity. Their work focused on testing properties of functions, and yielded\nnew lower bounds as well as simplified analyses of known lower bounds. Here, we\ntake a further step in generalizing the methodology of Blais et al. to analyze\nthe query complexity of graph parameter estimation problems. In particular, our\ntechnique decouples the lower bound arguments from the representation of the\ngraph, allowing it to work with any query type.\n We illustrate our technique by providing new simpler proofs of previously\nknown tight lower bounds for the query complexity of several graph problems:\nestimating the number of edges in a graph, sampling edges from an\nalmost-uniform distribution, estimating the number of triangles (and more\ngenerally, r-cliques) in a graph, and estimating the moments of the degree\ndistribution of a graph. We also prove new lower bounds for estimating the edge\nconnectivity of a graph and estimating the number of instances of any fixed\nsubgraph in a graph. We show that the lower bounds for estimating the number of\ntriangles and edge connectivity also hold in a strictly stronger computational\nmodel that allows access to uniformly random edge samples.\n