Applications of Random Algebraic Constructions to Hardness of Approximation.
Boris BukhKarthik C. S.Bhargav NarayananPublished in: FOCS (2022)
Keyphrases
- approximation algorithms
- random instances
- phase transition
- computational complexity
- central limit theorem
- approximation error
- closed form
- np hardness
- np complete
- boolean functions
- graphical models
- np hard
- error bounds
- markov chain
- efficient computation
- uniformly distributed
- queueing networks
- approximation methods
- agnostic learning
- approximation schemes
- information systems