Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation
From MaRDI portal
Publication:4609470
DOI10.1137/16M1075144zbMath1395.90199arXiv1605.04008MaRDI 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
convex optimizationstrongly regular graphsdistance-regular graphssemidefinite programmingmajorizationorbitopesinduced subgraph isomorphism
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Convex programming (90C25) Applications of mathematical programming (90C90)
Related Items
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
Cites Work
- 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 ℓ 1 minimization
- GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
