Optimal Low-Degree Hardness of Maximum Independent Set
We study the algorithmic task of finding a large independent set in a sparse Erd\H{o}s-R\'{e}nyi random graph with $n$ vertices and average degree $d$. The maximum independent set is known to have size $(2 \log d / d)n$ in the double limit $n \to \infty$ followed by $d \to \infty$, but the best known polynomial-time algorithms can only find an independent set of half-optimal size $(\log d / d)n$. We show that the class of low-degree polynomial algorithms can find independent sets of half-optimal size but no larger, improving upon a result of Gamarnik, Jagannath, and the author. This generalizes earlier work by Rahman and Vir\'ag, which proved the analogous result for the weaker class of local algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed that the maximum independent set has densit…
Hardness of Maximum Likelihood Learning of DPPs
Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative sub…
graph constructionPoint ProcessesInformation Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
Markov random fields area popular model for high-dimensional probability distributions. Over the years, many mathematical, statistical and algorithmic problems on them have been studied. Until recently, the only known al…
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the dis…
Near-Optimal Degree Testing for Bayes Nets
This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution $P$ over $\{0,1\}^n$, given sample access to $P$. We show that the sample complexity of th…