Sum-of-Squares Lower Bounds for Sparse Independent Set.

Chris Jones Aaron Potechin Goutham Rajendran Madhur Tulsiani Jeff Xu

Published in: FOCS (2021)

Keyphrases

independent set
lower bound
upper bound
branch and bound
maximum independent set
branch and bound algorithm
lower and upper bounds
objective function
np hard
maximum weight
vc dimension
high dimensional
worst case
multi dimensional