More Like this

1. Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles

   Bresler, Guy; Guo, Chenghao; Polyanskiy, Yury (November 2023, Foundations of Computer Science)

   We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd\H{o}s-R\'enyi , which has independent edges, we take the ambient graph to be the \emph{random graph with triangles} (RGT) obtained by adding triangles to . We show that the RGT can be efficiently mapped to the corresponding , and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on \emph{low sensitivity to perturbations}. 

   more » « less
2. Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

   Bresler, Guy; Jiang, Tianze (July 2023, Proceedings of Thirty Sixth Conference on Learning Theory)

   Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or re- covery, appear to have different computational limits. A detection-recovery gap for PDS was sub- stantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems. 

   more » « less
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. Random Subgraph Detection Using Queries

   Huleihel, W; Mazumdar, A; Pal, S (April 2024, Journal of machine learning research)

   The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an Erdös-R{\'e}nyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph. We also propose a polynomial-time algorithm which is able to detect the planted subgraph, albeit with more queries compared to the above lower bound. We conjecture that in the leftover regime, no polynomial-time algorithms exist. Our results resolve two open questions posed in the past literature. 

   more » « less
5. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2  

   Chudnovsky, Maria and (February 2021, MATRIX book series)

   null (Ed.)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less