A new approach to the planted clique problem

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Foundations of Software Technology and Theoretical Computer Science

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.FSTTCS.2008.1752
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• Tensor decomposition and approximation schemes for constraint satisfaction problems

  2005cited by this paper
• Random sampling and approximation of MAX-CSPs

  2003cited by this paper
• Random sampling and approximation of MAX-CSP problems

  2002cited by this paper
• Spectral partitioning of random graphs

  2001cited by this paper
• On the concentration of eigenvalues of random symmetric matrices

  2000cited by this paper
• Finding and certifying a large hidden clique in a semirandom graph

  2000cited by this paper
• Clique Is Hard to Approximate within n1-o(1)

  2000cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• Quick Approximation to Matrices and Applications

  1999cited by this paper
• Finding a large hidden clique in a random graph

  1998influential reference
• Hiding Cliques for Cryptographic Security

  1998cited by this paper
• Clique is hard to approximate within n/sup 1-/spl epsiv//

  1996cited by this paper
• Expected Complexity of Graph Partitioning Problems

  1995cited by this paper
• Large Cliques Elude the Metropolis Process

  1992cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• Reducibility among combinatorial problems" in complexity of computer computations

  1972cited by this paper

• A hierarchy of eigencomputations for polynomial optimization on the sphere

  2023cites this paper
• New SDP Roundings and Certifiable Approximation for Cubic Optimization

  2023cites this paper
• Average-Case Communication Complexity of Statistical Problems

  2021cites this paper
• Convex Formulation for Planted Quasi-Clique Recovery

  2021cites this paper
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

  2020cites this paper
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

  2019cites this paper
• On the subgraph query problem

  2019cites this paper
• Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing

  2019cites this paper
• The Hidden Hubs Problem

  2017cites this paper
• Learning Discrete Distributions from Untrusted Batches

  2017influential citation
• Random Matrices and the Sum-of-Squares Hierarchy

  2017cites this paper
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

  2016cites this paper
• Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy

  2016cites this paper
• Beyond Spectral: Tight Bounds for Planted Gaussians

  2016cites this paper
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

  2016cites this paper
• Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

  2016influential citation
• Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

  2016cites this paper
• Detecting highly cyclic structure with complex eigenpairs

  2016cites this paper
• Chi-squared Amplification: Identifying Hidden Hubs

  2016cites this paper
• SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four

  2015cites this paper
• Sum-of-squares Lower Bounds for Planted Clique

  2015cites this paper
• Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

  2015cites this paper
• A New Relaxation Approach to Normalized Hypergraph Cut

  2015cites this paper
• Testing for high‐dimensional geometry in random graphs

  2014cites this paper
• Explorations on high dimensional landscapes

  2014cites this paper
• MASTER OF SCIENCE

  2014cites this paper
• Consistency of Spectral Partitioning of Uniform Hypergraphs under Planted Partition Model

  2014cites this paper
• New tools for unsupervised learning

  2014cites this paper
• Search Time when Solving Random Jigsaw Puzzles with a Planted Solution by

  2014cites this paper
• A tensor approach to learning mixed membership community models

  2013cites this paper
• Branching Width when Solving Random Jigsaw Puzzles with a Planted Solution by

  2012cites this paper
• Finding Dense Structures in Graphs and Matrices

  2012influential citation
• Statistical algorithms and a lower bound for detecting planted cliques

  2012influential citation
• Optimal detection of sparse principal components in high dimension

  2012cites this paper
• Statistical Algorithms and a Lower Bound for Planted Clique

  2012cites this paper
• Improving landfill monitoring programs with the aid of geoelectrical-imaging techniques and geographical information systems

  2012cites this paper
• New approaches to integer programming

  2012cites this paper
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques

  2012cites this paper
• The Complexity of Statistical Algorithms

  2012cites this paper
• Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA

  2011cites this paper
• Inapproximability of NP-Complete Variants of Nash Equilibrium

  2011cites this paper
• Convex relaxation for the planted clique, biclique, and clustering problems

  2011cites this paper
• Algorithms for implicit hitting set problems

  2011cites this paper
• Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA

  2011cites this paper
• Finding Hidden Cliques in Linear Time with High Probability

  2010cites this paper
• A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification

  2010cites this paper
• Spectral methods for matrices and tensors

  2010cites this paper
• Finding hidden cliques in linear time

  2009cites this paper
• Extensions of principal components analysis

  2009influential citation
• Random Tensors and Planted Cliques

  2009cites this paper
• How hard is it to approximate the best Nash equilibrium?

  2009cites this paper