More Like this

1. Is Planted Coloring Easier than Planted Clique?

   Kothari, Pravesh; Vempala, Santosh S.; Wein, Alex; Xu, Jeff (January 2023, Conference on Learning Theory)
2. Strong recovery of geometric planted matchings

   https://doi.org/10.1137/1.9781611977073.36  

   Kunisky, Dmitriy; Niles-Weed, Jonathan (January 2022, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))
3. Finding a planted clique by adaptive probing

   https://doi.org/10.30757/ALEA.v17-30  

   Racz, Miklos Z; Schiffer, Benjamin (August 2020, Alea)

   null (Ed.)

   We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let $$G \sim G(n,1/2,k)$$ be a random graph on $$n$$ vertices with a planted clique of size $$k$$. We show that no algorithm that makes at most $q = o(n^2 / k^2 + n)$ adaptive queries to the adjacency matrix of $$G$$ is likely to find the planted clique. On the other hand, when $$k \geq (2+\epsilon) \log_2 n$$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $$q = O( (n^2 / k^2) \log^2 n + n \log n)$$ adaptive queries. For detection, the additive $$n$$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2 / k^2$ (up to logarithmic factors). 

   more » « less
4. Found graph data and planted vertex covers

   Benson, Austin R; Kleinberg, Jon (December 2018, Advances in neural information processing systems)

   A typical way in which network data is recorded is to measure all interactions involving a specified set of core nodes, which produces a graph containing this core together with a potentially larger set of fringe nodes that link to the core. Interactions between nodes in the fringe, however, are not present in the resulting graph data. For example, a phone service provider may only record calls in which at least one of the participants is a customer; this can include calls between a customer and a non-customer, but not between pairs of non-customers. Knowledge of which nodes belong to the core is crucial for interpreting the dataset, but this metadata is unavailable in many cases, either because it has been lost due to difficulties in data provenance, or because the network consists of “found data” obtained in settings such as counter-surveillance. This leads to an algorithmic problem of recovering the core set. Since the core is a vertex cover, we essentially have a planted vertex cover problem, but with an arbitrary underlying graph. We develop a framework for analyzing this planted vertex cover problem, based on the theory of fixed-parameter tractability, together with algorithms for recovering the core. Our algorithms are fast, simple to implement, and out-perform several baselines based on core-periphery structure on various real-world datasets. 

   more » « less
5. Detection-Recovery Gap for Planted Dense Cycles

   Mao, Cheng; Wein, Alexander S; Zhang, Shenduo (July 2023, Proceedings of Thirty Sixth Conference on Learning Theory)