7 citations · 18 across the 15 of their papers we have counts for
4 papers · 1 filter
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…
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,…
Stable Matchings with Restricted Preferences: Structure and Complexity
Christine T. Cheng, Will Rosenbaum
It is well known that every stable matching instance has a rotation poset that can be computed efficiently and the downsets of are in one-to-one correspondence wi…
PALS: Plesiochronous and Locally Synchronous Systems
Johannes Bund, Matthias Függer, Christoph Lenzen +2
Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to…