Back to search

Boston University

New algorithms and impossibility results under restricted interfaces

Abstract

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.

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 × 1

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Ristache, Dragos-Florian. New algorithms and impossibility results under restricted interfaces. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53606