Theory Seminar

Seminars
Assistant Professor
Computer Science Department
University of Illinois - Urbana-Champaign
Matrix Signings, Ramanujan Graphs and Non-Expanding Independent Sets
Friday, February 17, 2017 -
3:00pm to 4:30pm
ASA Conference Room 6115 
Gates Hillman Center
Abstract:

The spectra of signed matrices have played a fundamental role in social sciences, graph theory and control theory. They have been key to understanding balance in social networks, to counting perfect matchings in bipartite graphs, and to analyzing robust stability of dynamic systems involving uncertainties. More recently, the results of Marcus et al. have shown that an efficient algorithm to find a signing of a given adjacency matrix that minimizes the largest eigenvalue could immediately lead to efficient construction of Ramanujan expanders.

Motivated by these applications, this talk investigates natural spectral properties of signed matrices and address the computational problems of identifying signings with these spectral properties. There are three main results we will talk about: (a) NP-completeness of three signing related problems with (negative) implications to efficiently constructing expander graphs, (b) a complete characterization of graphs that have all their signed adjacency matrices be singular, which implies a polynomial-time algorithm to verify whether a given matrix has a signing that is invertible, and (c) a polynomial-time algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible signing.

About the Speaker

Keywords:
For More Information, Please Contact:

nlc@cs.cmu.edu