Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01nc580m775
 Title: An assortment of results in combinatorics and compressed sensing Authors: Alexeev, Boris Advisors: Conway, John H Contributors: Mathematics Department Subjects: Mathematics Issue Date: 2013 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01nc580m775 Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Mathematics

Files in This Item:
File Description SizeFormat
Alexeev_princeton_0181D_10753.pdf809.29 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.