Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems.

Oded Goldreich Guy N. Rothblum

Published in: FOCS (2018)

Keyphrases

average case
worst case
worst case analysis
uniform distribution
learning curves
upper bound
objective function
lower bound
high dimensional
np hard
small number
greedy algorithm
approximation algorithms
average case complexity