An assortment of results in combinatorics and compressed sensing

Abstract

We prove a variety of results spanning combinatorics, compressed sensing, and theoretical computer science. Our methods throughout are primarily combinatorial, but we also use algebraic techniques and occasionally estimates from analysis. We begin by proving lower and upper bounds for tensor rank, a purely algebraic quantity of importance to complexity theory. As the highlight, we improve the best known lower bounds for explicit tensors. We continue by proving some complexity-theoretic results of interest to compressed sensing. Specifically, given standard complexity-theoretic assumptions, we show that any natural extension of the Mumford-Shah functional is infeasible to compute, as is the problem of testing a frame for possessing full spark. Along the way, we both construct some explicit full spark frames and show that full spark frames are dense in the set of Parseval frames. We follow the theme of merging complexity and compressed sensing further by using insights from the theory of expander graphs to give an efficient procedure to reconstruct a signal from intensity measurements, a problem known as phase retrieval. Our procedure improves upon the efficiency of all previously-known methods. In the penultimate chapter, we complete the characterization of the basic classes in the proof of the strong perfect graph theorem. Finally, we resolve a 75-year old conjecture in combinatorial number theory due to Richard Rado.