Skip navigation
Please use this identifier to cite or link to this item:
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.
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 PDFView/Download

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