7 citations · 9 across the 2 of their papers we have counts for
4 papers
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Approximate Trace Reconstruction
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian +1
In the usual trace reconstruction problem, the goal is to exactly reconstruct an unknown string of length after it passes through a deletion channel many times independently, p…
Scheduling with Communication Delays via LP Hierarchies and Clustering
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +2
We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting,…
Reconstructing Trees from Traces
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian
We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes s…