Applications of Random Algebraic Constructions to Hardness of Approximation.
Boris BukhKarthik C. S.Bhargav NarayananPublished in: FOCS (2021)
Keyphrases
- central limit theorem
- approximation algorithms
- computational complexity
- evolutionary algorithm
- learning theory
- data sets
- approximation methods
- continuous functions
- approximation error
- closed form
- np complete
- difference equations
- worst case
- random instances
- mathematical theory
- agnostic learning
- phase transition
- efficient computation
- information theoretic
- higher order
- np hard
- website