Theory Seminar

Friday, February 17, 2017 - 3:00pm to 4:30pm

Location:

ASA Conference Room 6115 Gates Hillman Center

Speaker:

ALEXANDRA KOLLA, Assistant Professor http://akolla.cs.illinois.edu/

Event Website:

http://theory.cs.cmu.edu/seminars/

For More Information, Contact:

nlc@cs.cmu.edu

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:

Seminar Series