The Complexity of Average-Case Dynamic Subgraph Counting.

Monika Henzinger Andrea Lincoln Barna Saha

Published in: SODA (2022)

Keyphrases

average case
worst case
average case complexity
uniform distribution
np hard
worst case analysis
learning curves
upper bound
decision problems
learning algorithm
lower bound