Abstract:
Suppose we have two competing ideas/products/viruses that propagate over a social or other network. Suppose that they are strong/virulent enough, so that each, if left alone, could lead to an epidemic. What will happen when both operate on the network? What happens at the end, that is, which product will "win," in terms of highest market share?

First we study the case where two viruses are fully competitive/mutually exclusive (work from WWW 2012). One may naively expect that the better product (stronger virus) will just have a larger footprint, proportional to the quality ratio of the products (or strength ratio of the viruses). However, we prove the surprising result that, under realistic conditions, for any graph topology, the stronger virus completely wipes-out the weaker one ("winner-takes-all"). In addition to the proofs, we also demonstrate our result with simulations over diverse, real graph topologies and match our model against real data about competing products from Google Insights.

Second we study the case where the viruses are not mutually exclusive but have some variable amount of interaction (work from KDD 2012). For example, one type of flu may give partial immunity against some other similar disease, or a user could install and use both Firefox and Google Chrome. With our model we ask, what happens in-between the two extremes of "winner takes all" (as is the case with mutually exclusive viruses) and independent survival (as is the case with non-interacting viruses). We show that there is a phase transition: if the competition is harsher than a critical level, then "winner takes all;" otherwise, the weaker virus survives. We discuss (a) the problem definition, which is novel even in epidemiology literature (b) the phase-transition result and (c) experiments on real data, illustrating the suitability of our results.

Abstract:
A point set in the plane has many triangulations. One may define a measure of quality of a triangulation and ask for the triangulation which optimizes that quality. One such measure is the maximum angle, another the maximum area. For the former criteria, "edge insertion" is an algorithm that will find the optimum triangulation efficiently. Whereas, no polynomial time algorithm is known for maximum area, the so called minmax area triangulation problem. I will present the edge insertion algorithm and at the end will give a counterexample that shows edge insertion cannot be used for minmax area triangulation.

Abstract:
We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include furthest nearest neighbor, finding the optimal k-center clustering, smallest disk enclosing k points, kth largest distance, $k$th smallest m-nearest neighbor distance, kth heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more.
Joint work with Benjamin Raichel.
http://valis.cs.uiuc.edu/~sariel/papers/12/aggregate/

Abstract:

In this talk, I will present algorithms and data structures for the top-k nearest neighbor searching where the input points are exact and the query point is uncertain under the L1 distance metric in the plane. The uncertain query point is represented by a discrete probability density function, and the goal is to return the top-k expected nearest neighbors, which have the smallest expected distances to the query point. Given a set of n exact points in the plane, we build an O(n log n log log n)-size data structure in O(n log n log log n) time, such that for any uncertain query point with m possible locations and any integer k with 1 \leq k \leq n, the top-k expected nearest neighbors can be found in O(m log m + (k + m) log^2 n) time. Even for the special case where k = 1, our result is better than the previously best method (in PODS 2012), which requires O(n log^2 n) preprocessing time, O(n log^2 n) space, and O(m^2 log^3 n) query time. In addition, for the one-dimensional version of this problem, our approach can build an O(n)-size data structure in O(n log n) time that can support O(min{km, k + m log m} + log n) time queries.

Joint work with Haitao Wang, Utah State University. In the process of submitting to ESA 2013.