Boston University
New algorithms and impossibility results under restricted interfaces
Abstract
dc:description.abstractMany 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.
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
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ristache, Dragos-Florian
- Advisor dc:contributor.advisor
-
- Onak, Krzysztof
Subjects
dc:subject × 1Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53606