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

2020/09/12 by Yuetian Luo, Anru R. Zhang, Luo, Yuetian +1 · 2 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2009.05870

openalex publication_date 2020/09/12 · openalex created_date 2020/09/21 · openalex updated_date 2026/07/28

Abstract

We note the significance of hypergraphic planted clique (HPC) detection in\nthe investigation of computational hardness for a range of tensor problems. We\nask if more evidence for the computational hardness of HPC detection can be\ndeveloped. In particular, we conjecture if it is possible to establish the\nequivalence of the computational hardness between HPC and PC detection.\n

Cited by

• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Long Random Matrices and Tensor Unfolding

Related

• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits
• Statistical and computational thresholds for the planted k-densest sub-hypergraph problem
• The Strongish Planted Clique Hypothesis and Its Consequences
• Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique
• Worst-Case and Average-Case Hardness of Hypercycle and Database Problems