The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs.

Abhishek Dhawan Yuzhou Wang

Published in: CoRR (2024)

Keyphrases

low degree
agnostic learning
computational complexity
np complete
decision lists
high dimensional
decision rules
phase transition
learning theory
uniform distribution