Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation

DOI10.1137/16M1075144zbMath1395.90199arXiv1605.04008WikidataQ130122118 ScholiaQ130122118MaRDI QIDQ4609470

Utkan Onur Candogan, Venkat Chandrasekaran

Publication date: 3 April 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.04008

zbMATH Keywords

convex optimizationstrongly regular graphsdistance-regular graphssemidefinite programmingmajorizationorbitopesinduced subgraph isomorphism

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Convex programming (90C25) Applications of mathematical programming (90C90)

Related Items (3)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ A note on convex relaxations for the inverse eigenvalue problem ⋮ Convex graph invariant relaxations for graph edit distance

Uses Software

• SDPT3
• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Spectra of graphs
• Spreads in strongly regular graphs
• Nuclear norm minimization for the planted clique and biclique problems
• Multiplicative cones - a family of three eigenvalue graphs
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• On graphs with three eigenvalues
• Small regular graphs with four eigenvalues
• Regular graphs with four eigenvalues
• On characterizing certain graphs with four eigenvalues by their spectra
• Strongly regular graphs, partial geometries and partially balanced designs
• Exact matrix completion via convex optimization
• Lectures on Modern Convex Optimization
• Convex Graph Invariants
• Graph Implementations for Nonsmooth Convex Programs
• ORBITOPES
• A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Finding and certifying a large hidden clique in a semirandom graph
• Reducibility among Combinatorial Problems
• Clustering Social Networks
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES

This page was built for publication: Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation