47 citations · 124 across the 20 of their papers we have counts for
7 papers · 1 filter
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein +1
We study the computational complexity of two related problems: recovering a planted -coloring in , and finding efficiently verifiable witnesses of non--colorability…
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein
Suppose we are given an -dimensional order-3 symmetric tensor that is the sum of random rank-1 terms. The problem of recovering the rank-1…
Circuit Lower Bounds for the p-Spin Optimization Problem
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
We consider the problem of finding a near ground state of a -spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent w…
Optimal Low-Degree Hardness of Maximum Independent Set
Alexander S. Wein
We study the algorithmic task of finding a large independent set in a sparse Erdős-Rényi random graph with vertices and average degree . The maximum independent set is known…
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2
We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…
Counterexamples to the Low-Degree Conjecture
Justin Holmgren, Alexander S. Wein
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", whic…