Average-case hardness of RIP certification.

Tengyao Wang Quentin Berthet Yaniv Plan

Published in: NIPS (2016)

Keyphrases

average case
worst case
uniform distribution
worst case analysis
learning curves
upper bound
agnostic learning
phase transition
computational complexity
np hard
lower bound
average case complexity
vc dimension
approximation algorithms
online algorithms
sample size
training data