8 citations · 12 across the 4 of their papers we have counts for
5 papers
Low-degree phase transitions for detecting a planted clique in sublinear time
Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
We consider the problem of detecting a planted clique of size in a random graph on vertices. When the size of the clique exceeds , polynomial-time algorithms f…
Logspace Reducibility From Secret Leakage Planted Clique
Jay Mardia
The planted clique problem is well-studied in the context of observing, explaining, and predicting interesting computational phenomena associated with statistical problems. When eq…
Is the space complexity of planted clique recovery the same as that of detection?
Jay Mardia
We study the planted clique problem in which a clique of size k is planted in an Erdős-Rényi graph G(n, 1/2), and one is interested in either detecting or recovering this planted c…
Finding Planted Cliques in Sublinear Time
Jay Mardia, Hilal Asi, Kabir Aladin Chandrasekher
We study the planted clique problem in which a clique of size k is planted in an Erdos-Renyi graph G(n,1/2) and one is interested in recovering this planted clique. It is widely be…
Concentration Inequalities for the Empirical Distribution
Jay Mardia, Jiantao Jiao, Ervin Tánczos +2
We study concentration inequalities for the Kullback--Leibler (KL) divergence between the empirical distribution and the true distribution. Applying a recursion technique, we impro…