The Strongish Planted Clique Hypothesis and Its Consequences
summary
Postulates that for kappa = N^{0.1} planted clique cannot be solved in time N^{o(log N)} and uses a randomized graph product that samples N random L‑vertex subsets and connects two subset‑vertices iff their union is a clique. Completeness: with probability ≥0.9 at least K sampled subsets lie inside the planted clique, giving a K‑clique. Soundness: when G ~ G(N,1/2) any K‑set in the product has ≤O(K log N / L) edges with probability ≥0.9, yielding no polytime o(K) approximation for densest K‑subgraph and no N^{o(K)} time constant‑factor algorithm. strong-ish Planted Clique Hypothesis
AI-written summary · about