Finding planted cliques using gradient descent

DOI10.1137/24M1680489MaRDI QIDQ6956548zbMATH OpenFDO

Authors Reza Gheissari, Aukosh Jagannath, Yiming Xu

Publication date 18 July 2025

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1680489

zbMATH Keywords

gradient descentMarkov chain Monte Carlo methodplanted clique problemstatistical-to-computational gaps

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Cites work

• A nearly tight sum-of-squares lower bound for the planted clique problem
• A New Algorithm for the Robust Semi-random Independent Set Problem
• Algorithmic thresholds for tensor PCA
• Algorithms approaching the threshold for semi-random planted clique
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Asymptotic enumeration by degree sequence of graphs of high degree
• Coloring Random and Semi-Random k-Colorable Graphs
• Complexity of random smooth functions on the high-dimensional sphere
• Expected complexity of graph partitioning problems
• Finding and certifying a large hidden clique in a semirandom graph
• Finding hidden cliques in linear time with high probability
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Heuristics for semirandom graph problems
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Large Cliques Elude the Metropolis Process
• Learning from untrusted data
• Nuclear norm minimization for the planted clique and biclique problems
• On the integrality gap of degree-4 sum of squares for planted clique
• Optimal detection of sparse principal components in high dimension
• Random matrices and complexity of spin glasses
• Solving NP-hard semirandom graph problems in polynomial expected time
• Statistical algorithms and a lower bound for detecting planted cliques
• Sum-of-squares Lower Bounds for Planted Clique
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The landscape of the spiked tensor model
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set

This page was built for publication: Finding planted cliques using gradient descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6956548)