Back to search

Boston University

Improved algorithms and new models in property testing

Abstract

dc:description.abstract

We study sublinear-time algorithms for testing fundamental properties of functions and graphs. Sublinear-time algorithms run in time sublinear in the input size and are especially useful for processing massive datasets. We investigate variants of the property testing model, which was introduced by Rubinfeld and Sudan (SIAM J. Comput., 1996) and Goldreich, Goldwasser and Ron (J. ACM, 1998) to formally study sublinear-time algorithms. The focus of this thesis is on designing better property testers, deepening our understanding of their limitations, and proposing new angles for investigating sublinear-time algorithms. First, we study the problem of testing unateness of real-valued functions over high-dimensional domains. A function over a multi-dimensional domain is unate if, along each dimension, the function is either nonincreasing or nondecreasing. We give efficient unateness testers and prove that they are optimal. We then focus on testing monotonicity of functions when the input functions are partially corrupted or partially erased. We prove that, for some settings of parameters, testing monotonicity of functions with corrupted or erased values is exponentially harder than testing monotonicity of functions with neither corruptions nor erasures. We then investigate the parameters in terms of which the complexity of property testers should be expressed. The complexity of algorithms and, in particular, property testers is usually expressed in terms of the size of the input. We prove that certain parameters capture the complexity of testing problems better than the input size, providing compelling evidence that the input size may not always be the best parameter to express the complexity of sublinear-time algorithms. Finally, we turn our attention towards testing properties of graphs. We first provide an algorithm for testing connectedness of graphs and prove that it is optimal. We then define a new model for studying graphs with missing information and investigate the problems of testing connectedness and estimating the average degree of graphs in the new model.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pallavoor Suresh, Ramesh Krishnan
Advisor dc:contributor.advisor
  • Raskhodnikova, Sofya
ORCID dc:identifier.orcid

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/42025

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Pallavoor Suresh, Ramesh Krishnan. Improved algorithms and new models in property testing. doctoral thesis, Boston University, 2020. https://hdl.handle.net/2144/42025