Lily Chung

activity

20202026

most citedComplexity of Solo Chess with Unlimited Moves

2 citations · 2 across the 10 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Streaming Algorithms for Monotonicity Testing

Amir Azarmehr, Soheil Behnezhad, Lily Chung +3

Consider a poset - or equivalently an $n$ -vertex DAG $G = (V, E)$ - and a boolean function $f : V \to {0, 1}$ on its vertex set. We say $f$ is monotone if $f (u) \leq f (v)$ f…

cs.DS2022

Lower Bounds on Retroactive Data Structures

Lily Chung, Erik D. Demaine, Dylan Hendrickson +1

We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any o…

cs.DS2021

Improved Local Computation Algorithms for Constructing Spanners

Rubi Arviv, Lily Chung, Reut Levi +1

A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every $k$ , a spanner with size $O (n^{1 + 1/ k})$ and stretch $(2k+1)…