The complexity of approximating averages on bounded-degree graphs.

Andreas Galanis Daniel Stefankovic Eric Vigoda

Published in: FOCS (2020)

Keyphrases

bounded degree
graph theoretic
bounded treewidth
graph representation
databases
computational complexity
prior knowledge
graph structure
weighted graph
space complexity