Home
Resource
New computational aspects of discrepancy theory
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(1.24 MB)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Nikolov, Aleksandar. New computational aspects of discrepancy theory. Retrieved from https://doi.org/doi:10.7282/T3RN3749

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleNew computational aspects of discrepancy theory
NameNikolov, Aleksandar (author); Muthukrishnan, S. (chair); Saks, Michael (internal member); Kopparty, Swastik (internal member); Vadhan, Salil (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2014
Other Date2014-10 (degree)
SubjectComputer Science, Irregularities of distribution (Number theory)
Extent1 online resource (ix, 172 p. : ill.)
DescriptionThe main focus of this thesis work is computational aspects of discrepancy theory. Discrepancy theory studies how well discrete objects can approximate continuous ones. This question is ubiquitous in mathematics and computer science, and discrepancy theory has found numerous applications. In this thesis work, we (1) initiate the study of the polynomial time approximability of central discrepancy measures: we prove the first hardness of approximation results and design the first polynomial time approximation algorithms for combinatorial and hereditary discrepancy. We also (2) make progress on longstanding open problems in discrepancy theory, using insights from computer science: we give nearly tight hereditary discrepancy lower bounds for axis-aligned boxes in higher dimensions, and for homogeneous arithmetic progressions. Finally, we have (3) found new applications of discrepancy theory to (3a) fundamental questions in private data analysis and to (3b) communication complexity. In particular, we use discrepancy theory to design nearly optimal efficient algorithms for counting queries, in all parameter regimes considered in the literature. We also show that discrepancy lower bounds imply communication lower bounds for approximation problems in the one-way model. Directions for further research and connections to expander graphs, compressed sensing, and the design of approximation algorithms are outlined.
NotePh.D.
NoteIncludes bibliographical references
Noteby Aleksandar Nikolov
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3RN3749
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024