Description
TitleA simple algorithm for Horn's problem and two results on discrepancy
Date Created2019
Other Date2019-05 (degree)
Extent1 online resource (x, 115 pages)
DescriptionIn the second chapter we consider the discrepancy of permutation families. A k--permutation family on n vertices is a set-system consisting of the intervals of k permutations of [n]. Both 1- and 2-permutation families have discrepancy 1, that is, one can color the vertices red and blue such that the number of reds and blues in each edge differs by at most one. That is, their discrepancy is bounded by one. Beck conjectured that the discrepancy of for 3-permutation families is also O(1), but Newman and Nikolov disproved this conjecture in 2011. We give a simpler proof that Newman and Nikolov's sequence of 3-permutation families has discrepancy at least logarithmic in n. We also exhibit a new, tight lower bound for the related notion of root-mean-squared discrepancy of a 6-permutation family, and show new upper bounds on the root--mean--squared discrepancy of the union of set--systems.
In the third chapter we study the discrepancy of random matrices with m rows and n >> m independent columns drawn from a bounded lattice random variable, a model motivated by the Koml'os conjecture. We prove that, with high probability, the discrepancy is at most twice the l∞-covering radius of the lattice. As a consequence, the discrepancy of a m x n random t-sparse matrix is at most 1 with high probability for n ≥ m3 log2m, an exponential improvement over Ezra and Lovett (Ezra and Lovett, emph{Approx+Random}, 2015). More generally, we show polynomial bounds on the size of n required for the discrepancy to become at most twice the covering radius of the lattice with high probability.
In the fourth chapter, we obtain a simple algorithm to solve a class of linear algebraic problems. This class includes Horn's problem, the problem of finding Hermitian matrices that sum to zero with prescribed spectra. Other problems in this class arise in algebraic complexity, analysis, communication complexity, and quantum information theory. Our algorithm generalizes the work of (Garg et. al., 2016) and (Gurvits, 2004).
NotePh.D.
NoteIncludes bibliographical references
Genretheses, , ETD doctoral
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile