Random Tensors and Planted Cliques

Details Random Tensors and Planted Cliques Random Tensors and Planted Cliques

2009-05-14

arxiv.org/abs/0905.2381v1

Computer Science

Data Structures and Algorithms

Scientific paper

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. As a consequence, we get a tight connection between the planted clique problem and the problem of finding a vector that approximates the 2-norm of the r-parity tensor of a random graph. Our proof method is based on an inductive application of concentration of measure.

Affiliated with

Also associated with

No associations

Rating

Random Tensors and Planted Cliques does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Tensors and Planted Cliques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Tensors and Planted Cliques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-401318