Lower Bounds for Sums of Powers of Low Degree Univariates.
Neeraj KayalPascal KoiranTimothée PecatteChandan SahaPublished in: ICALP (1) (2015)
Keyphrases
- low degree
- lower bound
- integrality gap
- upper bound
- branch and bound
- threshold functions
- worst case
- uniform distribution
- objective function
- upper and lower bounds
- lower and upper bounds
- optimal solution
- np hard
- linear programming relaxation
- decision lists
- vc dimension
- agnostic learning
- sample complexity
- pac learning
- concept class
- supervised learning