[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Random Tensors and Planted Cliques

  • Conference paper
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2009, RANDOM 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5687))

  • 1868 Accesses

Abstract

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 [1] 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Frieze, A., Kannan, R.: A new approach to the planted clique problem. In: Proc. of FST & TCS (2008)

    Google Scholar 

  2. Karp, R.: The probabilistic analysis of some combinatorial search algorithms. In: Algorithms and Complexity: New Directions and Recent Results, pp. 1–19. Academic Press, London (1976)

    Google Scholar 

  3. Jerrum, M.: Large cliques elude the metropolis process. Random Structures and Algorithms 3(4), 347–360 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  4. Kucera, L.: Expected complexity of graph partitioning problems. Discrete Applied Mathematics 57, 193–212 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  5. Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Random Structures and Algorithms 13, 457–466 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  6. McSherry, F.: Spectral partitioning of random graphs. In: Proc. of FOCS, pp. 529–537 (2001)

    Google Scholar 

  7. Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. Random Structures and Algorithms 16(2), 195–208 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Füredi, Z., Komlós, J.: The eigenvalues of random symmetric matrices. Combinatorica 1(3), 233–241 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  9. Vu, V.H.: Spectral norm of random matrices. In: Proc. of STOC, pp. 423–430 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, 30332, USA

    S. Charles Brubaker & Santosh S. Vempala

Authors
  1. S. Charles Brubaker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Santosh S. Vempala
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. of Applied Math and Computer Science, The Weizmann Institute of Science, 76100, Rehovot, Israel

    Irit Dinur

  2. Institute for Computer Science and Applied Mathematics, University of Kiel, Olshausenstr. 40, 24098, Kiel, Germany

    Klaus Jansen

  3. Technion, Computer Science Department, 32000, Haifa, Israel

    Joseph Naor

  4. University of Geneva, Centre Universitaire d’Informatique, Battelle Bat. A, 7 rte de Drize, 1227, Carouge, Switzerland

    José Rolim

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Brubaker, S.C., Vempala, S.S. (2009). Random Tensors and Planted Cliques. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2009 2009. Lecture Notes in Computer Science, vol 5687. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03685-9_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-03685-9_31

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-03684-2

  • Online ISBN: 978-3-642-03685-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation