# Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

arXiv: https://arxiv.org/abs/2009.05870 · HTML: https://mlsanity.com/paper/2009.05870/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2020.

## Built on by (most cited first, 10 of 10)

- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Information Limits for Detecting a Subhypergraph](https://mlsanity.com/paper/2105.02259/) (2021)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [Tracking a Small Set of Experts in Online Convex Optimization](https://mlsanity.com/paper/2610.20416/) (2026)

## 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.