How to hide a clique?

DOI10.4230/LIPICS.ICALP.2020.44MaRDI QIDQ6842532zbMATH OpenFDO

Authors Uriel Feige

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.44

zbMATH Keywords

Lovasz theta functionplanted cliquerandom graphssemi-random model

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Algorithm Theory - SWAT 2004
• Expected complexity of graph partitioning problems
• Finding a Maximum Independent Set in a Sparse Random Graph
• Finding and certifying a large hidden clique in a semirandom graph
• Finding hidden cliques in linear time
• Finding hidden cliques in linear time with high probability
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Large Cliques Elude the Metropolis Process
• On the effect of randomness on planted 3-coloring models
• On the Shannon capacity of a graph
• Sum-of-squares Lower Bounds for Planted Clique
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set

This page was built for publication: How to hide a clique?

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