{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/39593"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/39593","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Analyzing massive datasets with missing entries: models and algorithms","abstract":"We initiate a systematic study of computational models to analyze algorithms for massive datasets with missing or erased entries and study the relationship of our models with existing algorithmic models for large datasets. We focus on algorithms whose inputs are naturally represented as functions, codewords, or graphs. First, we generalize the property testing model, one of the most widely studied models of sublinear-time algorithms, to account for the presence of adversarially erased function values. We design efficient erasure-resilient property testing algorithms for several fundamental properties of real-valued functions such as monotonicity, Lipschitz property, convexity, and linearity. We then investigate the problems of local decoding and local list decoding of codewords containing erasures. We show that, in some cases, these problems are strictly easier than the corresponding problems of decoding codewords containing errors. Moreover, we use this understanding to show a separation between our erasure-resilient property testing model and the (error) tolerant property testing model. The philosophical message of this separation is that errors occurring in large datasets are, in general, harder to deal with, than erasures. Finally, we develop models and notions to reason about algorithms that are intended to run on large graphs with missing edges. While running algorithms on large graphs containing several missing edges, it is desirable to output solutions that are close to the solutions output when there are no missing edges. With this motivation, we define average sensitivity, a robustness metric for graph algorithms. We discuss various useful features of our definition and design approximation algorithms with good average sensitivity bounds for several optimization problems on graphs. We also define a model of erasure-resilient sublinear-time graph algorithms and design an efficient algorithm for testing connectivity of graphs.","abstract_html":"We initiate a systematic study of computational models to analyze algorithms for massive datasets with missing or erased entries and study the relationship of our models with existing algorithmic models for large datasets. We focus on algorithms whose inputs are naturally represented as functions, codewords, or graphs. First, we generalize the property testing model, one of the most widely studied models of sublinear-time algorithms, to account for the presence of adversarially erased function values. We design efficient erasure-resilient property testing algorithms for several fundamental properties of real-valued functions such as monotonicity, Lipschitz property, convexity, and linearity. We then investigate the problems of local decoding and local list decoding of codewords containing erasures. We show that, in some cases, these problems are strictly easier than the corresponding problems of decoding codewords containing errors. Moreover, we use this understanding to show a separation between our erasure-resilient property testing model and the (error) tolerant property testing model. The philosophical message of this separation is that errors occurring in large datasets are, in general, harder to deal with, than erasures. Finally, we develop models and notions to reason about algorithms that are intended to run on large graphs with missing edges. While running algorithms on large graphs containing several missing edges, it is desirable to output solutions that are close to the solutions output when there are no missing edges. With this motivation, we define average sensitivity, a robustness metric for graph algorithms. We discuss various useful features of our definition and design approximation algorithms with good average sensitivity bounds for several optimization problems on graphs. We also define a model of erasure-resilient sublinear-time graph algorithms and design an efficient algorithm for testing connectivity of graphs.","abstract_has_math":false,"creators":["Varma, Nithin"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Raskhodnikova, Sofya"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-18T20:05:13Z","subjects":["Computer science","Average sensitivity","Erasure-resilient property testing","Erasures and errors","Local erasure-decoding","Sublinear-time algorithms"],"languages":["en_US"],"rights":["Attribution 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0002-1211-2566"],"render_values":[{"text":"0000-0002-1211-2566","href":"https://orcid.org/0000-0002-1211-2566","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/39593","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/39593","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F39593","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Raskhodnikova, Sofya"]},{"key":"dc:creator","label":"Author","values":["Varma, Nithin"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0002-1211-2566"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2020-03-02T13:58:47Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-03-02T13:58:47Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2020-02-24T20:02:09Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Average sensitivity","Erasure-resilient property testing","Erasures and errors","Local erasure-decoding","Sublinear-time algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/39593"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We initiate a systematic study of computational models to analyze algorithms for massive datasets with missing or erased entries and study the relationship of our models with existing algorithmic models for large datasets. We focus on algorithms whose inputs are naturally represented as functions, codewords, or graphs. First, we generalize the property testing model, one of the most widely studied models of sublinear-time algorithms, to account for the presence of adversarially erased function values. We design efficient erasure-resilient property testing algorithms for several fundamental properties of real-valued functions such as monotonicity, Lipschitz property, convexity, and linearity. We then investigate the problems of local decoding and local list decoding of codewords containing erasures. We show that, in some cases, these problems are strictly easier than the corresponding problems of decoding codewords containing errors. Moreover, we use this understanding to show a separation between our erasure-resilient property testing model and the (error) tolerant property testing model. The philosophical message of this separation is that errors occurring in large datasets are, in general, harder to deal with, than erasures. Finally, we develop models and notions to reason about algorithms that are intended to run on large graphs with missing edges. While running algorithms on large graphs containing several missing edges, it is desirable to output solutions that are close to the solutions output when there are no missing edges. With this motivation, we define average sensitivity, a robustness metric for graph algorithms. We discuss various useful features of our definition and design approximation algorithms with good average sensitivity bounds for several optimization problems on graphs. We also define a model of erasure-resilient sublinear-time graph algorithms and design an efficient algorithm for testing connectivity of graphs."]},{"key":"dc:title","label":"Title","values":["Analyzing massive datasets with missing entries: models and algorithms"]}]}],"canonical_facts":{"dc:contributor.advisor":["Raskhodnikova, Sofya"],"dc:creator":["Varma, Nithin"],"dc:date.accessioned":["2020-03-02T13:58:47Z"],"dc:date.available":["2020-03-02T13:58:47Z"],"dc:date.issued":["2019"],"dc:date.updated":["2020-02-24T20:02:09Z"],"dc:description.abstract":["We initiate a systematic study of computational models to analyze algorithms for massive datasets with missing or erased entries and study the relationship of our models with existing algorithmic models for large datasets. We focus on algorithms whose inputs are naturally represented as functions, codewords, or graphs. First, we generalize the property testing model, one of the most widely studied models of sublinear-time algorithms, to account for the presence of adversarially erased function values. We design efficient erasure-resilient property testing algorithms for several fundamental properties of real-valued functions such as monotonicity, Lipschitz property, convexity, and linearity. We then investigate the problems of local decoding and local list decoding of codewords containing erasures. We show that, in some cases, these problems are strictly easier than the corresponding problems of decoding codewords containing errors. Moreover, we use this understanding to show a separation between our erasure-resilient property testing model and the (error) tolerant property testing model. The philosophical message of this separation is that errors occurring in large datasets are, in general, harder to deal with, than erasures. Finally, we develop models and notions to reason about algorithms that are intended to run on large graphs with missing edges. While running algorithms on large graphs containing several missing edges, it is desirable to output solutions that are close to the solutions output when there are no missing edges. With this motivation, we define average sensitivity, a robustness metric for graph algorithms. We discuss various useful features of our definition and design approximation algorithms with good average sensitivity bounds for several optimization problems on graphs. We also define a model of erasure-resilient sublinear-time graph algorithms and design an efficient algorithm for testing connectivity of graphs."],"dc:identifier.orcid":["0000-0002-1211-2566"],"dc:identifier.uri":["https://hdl.handle.net/2144/39593"],"dc:language.iso":["en_US"],"dc:rights":["Attribution 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Computer science","Average sensitivity","Erasure-resilient property testing","Erasures and errors","Local erasure-decoding","Sublinear-time algorithms"],"dc:title":["Analyzing massive datasets with missing entries: models and algorithms"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T20:05:13Z"}