conftrace_

planted clique

17 papers

Explore in graph

Also known as

PC

Co-occurring keywords

hypothesis testing (254) computational lower bound (7) low-degree polynomial (17) computational hardness (24) average-case reduction (3) sparse principal component analysis (47) random graph (47) phase transition (92) spectral method (204) lower bound (173)

Papers

Low-degree phase transitions for detecting a planted clique in sublinear time COLT 2024
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique COLT 2023
Is Planted Coloring Easier than Planted Clique? COLT 2023
Sparse PCA Beyond Covariance Thresholding COLT 2023
Average-Case Communication Complexity of Statistical Problems COLT 2021
Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent COLT 2021
Reducibility and Statistical-Computational Gaps from Secret Leakage COLT 2020
Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection COLT 2020
Universality of Computational Lower Bounds for Submatrix Detection COLT 2019
Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness COLT 2019
Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure COLT 2018
The Hidden Hubs Problem COLT 2017
Computational Lower Bounds for Community Detection on Random Graphs COLT 2015
Label optimal regret bounds for online local learning COLT 2015
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems COLT 2015
Complexity Theoretic Lower Bounds for Sparse Principal Component Detection COLT 2013
The Lovász ϑ function, SVMs and finding large dense subgraphs NIPS 2012