Show simple item record

dc.contributor.advisorRaskhodnikova, Sofyaen_US
dc.contributor.authorPallavoor Suresh, Ramesh Krishnanen_US
dc.date.accessioned2021-02-11T18:14:59Z
dc.date.available2021-02-11T18:14:59Z
dc.date.issued2020
dc.identifier.urihttps://hdl.handle.net/2144/42025
dc.description.abstractWe 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.en_US
dc.language.isoen_US
dc.rightsAttribution 4.0 Internationalen_US
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.subjectComputer scienceen_US
dc.subjectProperty testingen_US
dc.subjectSublinear algorithmsen_US
dc.titleImproved algorithms and new models in property testingen_US
dc.typeThesis/Dissertationen_US
dc.date.updated2021-02-11T03:21:09Z
etd.degree.nameDoctor of Philosophyen_US
etd.degree.leveldoctoralen_US
etd.degree.disciplineComputer Scienceen_US
etd.degree.grantorBoston Universityen_US
dc.identifier.orcid0000-0003-1060-7466


This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's license is described as Attribution 4.0 International