8 citations · 18 across the 3 of their papers we have counts for
5 papers
Incremental Voronoi Diagrams
Sarah R. Allen, Luis Barba, John Iacono +1
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram (and several vari…
How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
Let be a -ary predicate over a finite alphabet. Consider a random CSP instance over variables with constraints. When the instance will be unsa…
Conditioning and covariance on caterpillars
Sarah R. Allen, Ryan O'Donnell
Let be joint -valued random variables. It is known that conditioning on a random subset of of them reduces their average pairwise covarianc…
Evaluation of DNF Formulas
Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik +1
Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function on an unknown input , when each bit of of can onl…
Packing identical simple polygons is NP-hard
Sarah R. Allen, John Iacono
Given a small polygon S, a big simple polygon B and a positive integer k, it is shown to be NP-hard to determine whether k copies of the small polygon (allowing translation and rot…