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

Yuetian Luo, Anru R Zhang
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3852-3856, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-luo20a, title = {Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection}, author = {Luo, Yuetian and Zhang, Anru R}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {3852--3856}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/luo20a/luo20a.pdf}, url = {https://proceedings.mlr.press/v125/luo20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection %A Yuetian Luo %A Anru R Zhang %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-luo20a %I PMLR %P 3852--3856 %U https://proceedings.mlr.press/v125/luo20a.html %V 125 %X 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.
APA
Luo, Y. & Zhang, A.R.. (2020). Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:3852-3856 Available from https://proceedings.mlr.press/v125/luo20a.html.

Related Material