Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
Not on the map. Why?
Abstract (arXiv)
We note the significance of hypergraphic planted clique (HPC) detection in the investigation of computational hardness for a range of tensor problems. We ask if more evidence for the computational hardness of HPC detection can be developed. In particular, we conjecture if it is possible to establish the equivalence of the computational hardness between HPC and PC detection.
Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). First posted on arXiv 12 Sep 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 7; 2022: 1; 2023: 1; 2024: 0; 2025: 0; 2026: 1.
10 papers.
- 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
- 2021Long Random Matrices and Tensor Unfoldingcited by 10
- 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
- 2021Sharp detection boundaries on testing dense subhypergraphcited by 5
- 2021Heterogeneous Dense Subhypergraph Detectioncited by 2
- 2021Information Limits for Detecting a Subhypergraphcited by 2
- 2021Community detection in censored hypergraphcited by 1
- 2021Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapescited by 0
- 2023Statistical and computational rates in high rank tensor estimationcited by 0
- 2026Tracking a Small Set of Experts in Online Convex Optimizationcited by 0
- 2026Tracking a Small Set of Experts in Online Convex Optimization14 Oct 2026
- 2023Statistical and computational rates in high rank tensor estimation8 Apr 2023
- 2022Higher degree sum-of-squares relaxations robust against oblivious outliers14 Nov 2022
- 2021Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes23 Dec 2021
- 2021Community detection in censored hypergraph4 Nov 2021
- 2021Long Random Matrices and Tensor Unfolding19 Oct 2021
- 2021Information Limits for Detecting a Subhypergraph5 May 2021
- 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence24 Apr 2021
- 2021Heterogeneous Dense Subhypergraph Detection8 Apr 2021
- 2021Sharp detection boundaries on testing dense subhypergraph12 Jan 2021