| 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. |
