Finding a planted clique by adaptive probing
From MaRDI portal
Publication:5126325
zbMath1448.05181arXiv1903.12050MaRDI QIDQ5126325
Miklós Z. Rácz, Benjamin Schiffer
Publication date: 16 October 2020
Full work available at URL: https://arxiv.org/abs/1903.12050
Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Optimal detection of sparse principal components in high dimension
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Expected complexity of graph partitioning problems
- Hiding cliques for cryptographic security
- Sparse CCA: adaptive estimation and computational barriers
- Finding paths in sparse random graphs requires many queries
- Finding Hamilton cycles in random graphs with few queries
- Efficient noise-tolerant learning from statistical queries
- Online Ramsey Numbers and the Subgraph Query Problem
- Large Cliques Elude the Metropolis Process
- Cliques in random graphs
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
- Finding cliques using few probes
- Finding Hidden Cliques in Linear Time with High Probability
- Unnamed Item
- Unnamed Item
This page was built for publication: Finding a planted clique by adaptive probing
