TITLE: Advancements in Inverse Problems in Combinatorial Spectral Theory

ABSTRACT: Combinatorial spectral theory has yielded many gains in theoretical and practical computer science in recent years, from GNN embeddings based on spectral metrics to graph inference algorithms with concrete applications. In this work several open problems are given proposed solutions. (1) Randomized reconstruction algorithms based on shortest path queries are generalized to randomized spectral analogs. (2) Graph completion algorithms are generalized to simplicial complex reconstruction algorithms. (3) Psuedo-inverse updating and graph updating algorithms are extended to a spectral query model.

MAJOR ADVISOR: Amir Nayyeri
CO-MAJOR ADVISOR: Huck Bennett
COMMITTEE: Glencora Borradaile
COMMITTEE: Yue Zhang
COMMITTEE: Eugene Zhang
GCR: Clayton Petsche