13 citations · 34 across the 10 of their papers we have counts for
4 papers · 1 filter
Finding a planted clique by adaptive probing
Miklós Z. Rácz, Benjamin Schiffer
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. W…
Finding cliques using few probes
Uriel Feige, David Gamarnik, Joe Neeman +2
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an vertex graph, and need to output a clique. We show that if the input gr…
Optimal control for diffusions on graphs
Laura Florescu, Yuval Peres, Miklos Z. Racz
Starting from a unit mass on a vertex of a graph, we investigate the minimum number of "\emph{controlled diffusion}" steps needed to transport a constant mass outside of the ba…
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
Ronen Eldan, Miklós Rácz, Tselil Schramm
We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, pe…