Source author record

Sarah R. Allen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry Information Theory math.IT math.PR

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Incremental Voronoi Diagrams

We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $\mathcal{V}(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added. We define a general update operation for planar graphs modeling the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in $\mathbb{R}^3$ . We show that the amortized number of edge insertions and removals needed to add a new site is $O(\sqrt{n})$ . A matching $Ω(\sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph of the diagram is a tree. This contrasts with the $O(\log{n})$ upper bound of Aronov et al. (2006) for farthest-point Voronoi diagrams when the points are inserted in order along their convex hull. We present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position. This structure supports the insertion of a new site $p$ and finds the asymptotically minimal number $K$ of edge insertions and removals needed to obtain the diagram of $S \cup \{p\}$ from the diagram of $S$ , in time $O(K\,\mathrm{polylog}\ n)$ worst case, which is $O(\sqrt{n}\;\mathrm{polylog}\ n)$ amortized by the aforementioned result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained at all times and can be traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in $O(\log n)$ time, or to determine whether two given sites are neighbors in the Delaunay triangulation.

preprint2015arXiv

How to refute a random CSP

Let $P$ be a $k$ -ary predicate over a finite alphabet. Consider a random CSP $(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m \gg n$ the instance $I$ will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When $P$ is the $3$ -ary OR predicate, this is the well studied problem of refuting random $3$ -SAT formulas, and an efficient algorithm is known only when $m \gg n^{3/2}$ . Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a $k$ -ary predicate, having $m \gg n^{\lceil k/2 \rceil}$ constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if $P$ fails to support a $t$ -wise uniform distribution, then there is an efficient algorithm that refutes random CSP $(P)$ instances $I$ whp when $m \gg n^{t/2}$ . Indeed, our algorithm will "somewhat strongly" refute $I$ , certifying $\mathrm{Opt}(I) \leq 1-Ω_k(1)$ , if $t = k$ then we get the strongest possible refutation, certifying $\mathrm{Opt}(I) \leq \mathrm{E}[P] + o(1)$ . This last result is new even in the context of random $k$ -SAT. Regarding the optimality of our $m \gg n^{t/2}$ requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP $(P)$ may be impossible when $m \ll n^{t/2}$ . Thus there is an indication our algorithm's dependence on $m$ is optimal for every $P$ , at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the $O(1)$ -round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.

preprint2014arXiv

Conditioning and covariance on caterpillars

Let $X_1, \dots, X_n$ be joint $\{ \pm 1\}$ -valued random variables. It is known that conditioning on a random subset of $O(1/ε^2)$ of them reduces their average pairwise covariance to below $ε$ (in expectation). We conjecture that $O(1/ε^2)$ can be improved to $O(1/ε)$ . The motivation for the problem and our conjectured improvement comes from the theory of global correlation rounding for convex relaxation hierarchies. We suggest attempting the conjecture in the case that $X_1, \dots, X_n$ are the leaves of an information flow tree. We prove the conjecture in the case that the information flow tree is a caterpillar graph (similar to a two-state hidden Markov model).

preprint2014arXiv

Evaluation of DNF Formulas

Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function $f$ on an unknown input $x$ , when each bit of $x_i$ of $x$ can only be determined by paying a given associated cost $c_i$ . Further, $x$ is drawn from a given product distribution: for each $x_i$ , $Prob[x_i=1] = p_i$ , and the bits are independent. The goal is to minimize the expected cost of evaluation. Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function $f$ on an unknown input $x$ , when each bit of $x_i$ of $x$ can only be determined by paying a given associated cost $c_i$ . Further, $x$ is drawn from a given product distribution: for each $x_i$ , $Prob[x_i=1] = p_i$ , and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

preprint2012arXiv

Packing identical simple polygons is NP-hard

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 rotation) can be placed in the big polygon without overlap. Previous NP-hardness results were only known in the case where the big polygon is allowed to be non-simple. A novel reduction from Planar-Circuit-SAT is presented where a small polygon is constructed to encode the entire circuit.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.