7 citations · 12 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2020
Almost Optimal Bounds for Sublinear-Time Sampling of -Cliques: Sampling Cliques is Harder Than Counting
Talya Eden, Dana Ron, Will Rosenbaum
In this work, we consider the problem of sampling a -clique in a graph from an almost uniform distribution in sublinear time in the general graph query model. Specifically the a…
cs.DS2020★ 2 cited
Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth
Christine T. Cheng, Will Rosenbaum
In this paper, we consider the problem of counting and sampling structures in graphs. We define a class of "edge universal labeling problems"---which include proper -colorings,…
cs.DS2019★ 1 cited
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing
Avery Miller, Boaz Patt-Shamir, Will Rosenbaum
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate and burstiness . In this model, we analyze th…