{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/53606"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/53606","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"New algorithms and impossibility results under restricted interfaces","abstract":"Many algorithmic tasks require answering global questions in restricted environments. In idealized settings, models often assume that algorithms have complete access to their input and unrestricted computational resources. In practice, however, they rarely have full access to a global object or unrestricted ability to modify it. They may be constrained by memory, query complexity, intervention budgets, adversarial interaction, and local or partial access models. In this thesis, we study what can be achieved under such restrictions, both through the design of efficient algorithms and through lower bounds that identify inherent barriers. We develop this theme across four lines of work. First, we study the adaptive use of Count-Min Sketch, a widely used streaming frequency estimator for memory constrained environments. We characterize when compact sketches remain reliable under adversarial interaction and when they become vulnerable to adaptive attacks. Second, we design algorithms and lower bounds for testing connectedness of large images from pixel queries, where the goal is to decide a global structural property using sublinear access to the input. Third, we study opinion dynamics control, where an intervention changes only a small part of a network but aims to affect global equilibrium statistics, including wisdom-of-crowds error, polarization, medians, and quantiles. In this network setting the input may be fully known, but computational hardness and limited intervention budgets impose the relevant barriers. Lastly, we investigate local computation algorithms for graph labeling, with a focus on lower bounds. This line of work sharpens the same theme in a fully local setting: even when a valid labeling is easy to construct centrally, answering vertex queries consistently can require nearly exponential probe complexity in the maximum degree.","abstract_html":"Many algorithmic tasks require answering global questions in restricted environments. In idealized settings, models often assume that algorithms have complete access to their input and unrestricted computational resources. In practice, however, they rarely have full access to a global object or unrestricted ability to modify it. They may be constrained by memory, query complexity, intervention budgets, adversarial interaction, and local or partial access models. In this thesis, we study what can be achieved under such restrictions, both through the design of efficient algorithms and through lower bounds that identify inherent barriers. We develop this theme across four lines of work. First, we study the adaptive use of Count-Min Sketch, a widely used streaming frequency estimator for memory constrained environments. We characterize when compact sketches remain reliable under adversarial interaction and when they become vulnerable to adaptive attacks. Second, we design algorithms and lower bounds for testing connectedness of large images from pixel queries, where the goal is to decide a global structural property using sublinear access to the input. Third, we study opinion dynamics control, where an intervention changes only a small part of a network but aims to affect global equilibrium statistics, including wisdom-of-crowds error, polarization, medians, and quantiles. In this network setting the input may be fully known, but computational hardness and limited intervention budgets impose the relevant barriers. Lastly, we investigate local computation algorithms for graph labeling, with a focus on lower bounds. This line of work sharpens the same theme in a fully local setting: even when a valid labeling is easy to construct centrally, answering vertex queries consistently can require nearly exponential probe complexity in the maximum degree.","abstract_has_math":false,"creators":["Ristache, Dragos-Florian"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Onak, Krzysztof"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T19:50:13Z","subjects":["Computer science"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2144/53606","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/53606","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%2F53606","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Onak, Krzysztof"]},{"key":"dc:creator","label":"Author","values":["Ristache, Dragos-Florian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-10-05T18:03:08Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-10-05T18:03:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2026-10-02T22:15:32Z"]},{"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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/53606"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["2026"]},{"key":"dc:description.abstract","label":"Abstract","values":["Many algorithmic tasks require answering global questions in restricted environments. In idealized settings, models often assume that algorithms have complete access to their input and unrestricted computational resources. In practice, however, they rarely have full access to a global object or unrestricted ability to modify it. They may be constrained by memory, query complexity, intervention budgets, adversarial interaction, and local or partial access models. In this thesis, we study what can be achieved under such restrictions, both through the design of efficient algorithms and through lower bounds that identify inherent barriers. We develop this theme across four lines of work. First, we study the adaptive use of Count-Min Sketch, a widely used streaming frequency estimator for memory constrained environments. We characterize when compact sketches remain reliable under adversarial interaction and when they become vulnerable to adaptive attacks. Second, we design algorithms and lower bounds for testing connectedness of large images from pixel queries, where the goal is to decide a global structural property using sublinear access to the input. Third, we study opinion dynamics control, where an intervention changes only a small part of a network but aims to affect global equilibrium statistics, including wisdom-of-crowds error, polarization, medians, and quantiles. In this network setting the input may be fully known, but computational hardness and limited intervention budgets impose the relevant barriers. Lastly, we investigate local computation algorithms for graph labeling, with a focus on lower bounds. This line of work sharpens the same theme in a fully local setting: even when a valid labeling is easy to construct centrally, answering vertex queries consistently can require nearly exponential probe complexity in the maximum degree."]},{"key":"dc:title","label":"Title","values":["New algorithms and impossibility results under restricted interfaces"]}]}],"canonical_facts":{"dc:contributor.advisor":["Onak, Krzysztof"],"dc:creator":["Ristache, Dragos-Florian"],"dc:date.accessioned":["2026-10-05T18:03:08Z"],"dc:date.available":["2026-10-05T18:03:08Z"],"dc:date.issued":["2026"],"dc:date.updated":["2026-10-02T22:15:32Z"],"dc:description":["2026"],"dc:description.abstract":["Many algorithmic tasks require answering global questions in restricted environments. In idealized settings, models often assume that algorithms have complete access to their input and unrestricted computational resources. In practice, however, they rarely have full access to a global object or unrestricted ability to modify it. They may be constrained by memory, query complexity, intervention budgets, adversarial interaction, and local or partial access models. In this thesis, we study what can be achieved under such restrictions, both through the design of efficient algorithms and through lower bounds that identify inherent barriers. We develop this theme across four lines of work. First, we study the adaptive use of Count-Min Sketch, a widely used streaming frequency estimator for memory constrained environments. We characterize when compact sketches remain reliable under adversarial interaction and when they become vulnerable to adaptive attacks. Second, we design algorithms and lower bounds for testing connectedness of large images from pixel queries, where the goal is to decide a global structural property using sublinear access to the input. Third, we study opinion dynamics control, where an intervention changes only a small part of a network but aims to affect global equilibrium statistics, including wisdom-of-crowds error, polarization, medians, and quantiles. In this network setting the input may be fully known, but computational hardness and limited intervention budgets impose the relevant barriers. Lastly, we investigate local computation algorithms for graph labeling, with a focus on lower bounds. This line of work sharpens the same theme in a fully local setting: even when a valid labeling is easy to construct centrally, answering vertex queries consistently can require nearly exponential probe complexity in the maximum degree."],"dc:identifier.uri":["https://hdl.handle.net/2144/53606"],"dc:language.iso":["en_US"],"dc:subject":["Computer science"],"dc:title":["New algorithms and impossibility results under restricted interfaces"],"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-18T19:50:13Z"}