Back to search

Cornell University

Sublinear Algorithms for Statistical, Markov Chain, and Binpacking Problems

Abstract

dc:description.abstract

We consider the problem of how to construct algorithms which deal efficiently with large amounts of data. We give new algorithms which use time and communication resources that are sublinear in the problem size for problems in various domains including statistics and combinatorics. We first consider properties of random variables. We begin with the problem of distinguishing whether two distributions over the same domain are close or far in both the L1 and the L2 norms. We investigate two models for representing a distribution. In one model, elements of a sample space are generated on request according to a fixed but unknown distribution. In the other, the probability assigned to each element is given explicitly in an array. We present algorithms in two settings: (1) when both distributions are represented in the first model; and, (2) when one of each representation is given. We show that the first setting is provably easier than the second setting. Next we give algorithms for testing whether two random variables are independent. In all of our algorithms, the number of samples required from the input distributions is sublinear in the domain size and nearly optimal. We then consider properties of data. Specifically, we give an algorithm which determines if a Markov Chain is rapidly mixing in sublinear time, assuming the input is in a form which allows for easy generation of sequential nodes in a random walk. Our test distinguishes Markov chains which are rapidly mixing from those which cannot be made rapidly mixing by changing a small number of edges. Finally we turn to a model in which the help of an untrusted entity is used to reliably solve a problem in sublinear time. For the problem of multidimensional bin-packing, we give an algorithm which can verify the goodness of a potential solution in sublinear time. To do this we develop tools which allow one to test that a function is approximately monotone.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • White, Patrick Edward
Chair dc:contributor.chair
  • Tardos, Éva
Committee members dc:contributor.committeemember
  • Shmoys, David B.
  • Selman, Bart
  • Rubinfeld, Ronitt

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
13119772
Dc Identifier Other
ProQuest Submission ID: 11570
ProQuest Publication ID: 22584375

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

White, Patrick Edward. Sublinear Algorithms for Statistical, Markov Chain, and Binpacking Problems. Doctor of Philosophy thesis, 2019. https://hdl.handle.net/1813/69986