Fetching the paper…

Reading the bibliography…

2009

Random Tensors and Planted Cliques

Brubaker, S. Charles, Vempala, Santosh

Original
PDF
Post on X

Understand

The r-parity tensor of a graph is a generalization of the adjacency matrix, where the tensor's entries denote the parity of the number of edges in subgraphs induced by r distinct vertices.

For r=2, it is the adjacency matrix with 1's for edges and -1's for nonedges.
It is well-known that the 2-norm of the adjacency matrix of a random graph is O(\sqrt{n}).
Here we show that the 2-norm of the r-parity tensor is at most f(r)\sqrt{n}\log^{O(r)}n, answering a question of Frieze and Kannan who proved this for r=3.

Random Tensors and Planted Cliques · Around

Built on

The probabilistic analysis of some combinatorial search algorithms
R. Karp · 1976
Earlier work this paper cites.
The eigenvalues of random symmetric matrices
Z. Füredi and J. Komlós · 1981
Earlier work this paper cites.
Large cliques elude the metropolis process
M. Jerrum · 1992
Earlier work this paper cites.

Similar

Expected complexity of graph partitioning problems
L. Kucera · 1995
Cited alongside, same era.
Finding a large hidden clique in a random graph
N. Alon, M. Krivelevich, and B. Sudakov · 1998
Cited alongside, same era.
Finding and certifying a large hidden clique in a semirandom graph
U. Feige and R. Krauthgamer · 2000
Cited alongside, same era.

Then

Spectral partitioning of random graphs
F. McSherry · 2001
Later among the works it cites.
Spectral norm of random matrices
Original
V. H. Vu · 2005
Later among the works it cites.
A new approach to the planted clique problem
A. Frieze and R. Kannan · 2008
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…