Abstract:

For d-dimensional point sets A,B, |A| = |B| = n, and a parameter \eps > 0, we present an algorithm that computes, in near-linear time, a matching whose cost is within (1 +\eps) of optimal perfect matching; the previously best known algorithm takes O(n^{1.5}) time.

We show how to approximate the L_p-norm using a distance function d(.,.) based on a randomly shifted quad-tree. Our algorithm iteratively generates an approximate minimum-cost augmenting path under d(.,.) in time proportional to the the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O((n/\eps) log n), implying a near-linear running time of the algorithm.

Joint work with Pankaj Agarwal. (To Appear in STOC'12)

Abstract:

We introduce a novel framework for computing optimal randomized security policies in networked domains which extends previous approaches in several ways. First, we extend previous linear programming techniques for Stackelberg security games to incorporate benefits and costs of arbitrary security configurations on individual assets. Second, we offer a principled model of failure cascades that allows us to capture both the direct and indirect value of assets, and extend this model to capture uncertainty about the structure of the interdependency network. Third, we extend the linear programming formulation to account for exogenous (random) failures in addition to targeted attacks. The goal of our work is two-fold. First, we aim to develop techniques for computing optimal security strategies in realistic settings involving interdependent security. To this end, we evaluate the value of our technical contributions in comparison with previous approaches, and show that our approach yields much better defense policies and scales to realistic graphs. Second, our computational framework enables us to attain theoretical insights about security on networks. As an example, we explore in depth the question of network resilience to targeted attacks that has piqued the interest of network science researchers in recent years, and demonstrate that our model, which (unlike previous models) allows endogenous defense decisions, paints a more complete picture than previous work.

Work by Sanjeev Arora , Elad Hazan , Satyen Kale
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.8450
Abstract:

Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very similar and rely on an exponential potential function.

We present a simple meta algorithm that unifies these disparate algorithms and drives them as simple instantiations of the meta algorithm.

Time: 11:45am - 12:45pm
Location: D106 LSRC, Duke

Abstract:
Describable visual attributes are labels that can be given to an image to describe its appearance. For example, faces can be described using the attributes "gender", "age", or "jaw shape." The advantages of an attribute-based representation for vision tasks are manifold: they can be composed to create descriptions at various levels of specificity; they are generalizable, as they can be learned once and then applied to recognize new objects or categories without any further training; and they are efficient, possibly requiring exponentially fewer attributes (and training data) than explicitly naming each category.

We show how one can create and label large datasets of real-world images to train classifiers which measure the presence, absence, or degree to which an attribute is expressed in images. These classifiers can then automatically label new images. We demonstrate the effectiveness of using attributes for a variety of tasks, including search, recognition, automatic image editing, and more.

This talk focuses on images of faces and the attributes used to describe them, but shows how the concepts can be applied to other domains as well, such as plants.

Bio:
--------
Neeraj Kumar is a postdoctoral research scientist at the University of Washington, working with Steve Seitz. He received a Ph.D. in Computer Science at Columbia University in 2011, where he was co-advised by Peter Belhumeur and Shree Nayar. His main research interests are at the intersection of computer vision and machine learning, developing techniques that leverage large collections of real-world images for a variety of applications. He is particularly interested in the use of intermediate representations such as parts and attributes, both for improving performance on classical vision tasks such as search and recognition, as well as for creating novel applications such as automatic face replacement and exploration of image collections.

Abstract:
Given a point cloud X sampled from or near a Riemannian manifold M embedded in high-dimensional Euclidean space, one often wants to build a metric on X which closely mirrors the geodesic metric on the manifold M. We present an algorithm which uses persistent homology to build such a metric, and provide theoretical guarantees, as well as experimental evidence, of its accuracy. Finally, we discuss ways in which this new metric can improve many standard non-linear dimension reduction techniques, including IsoMap and Locally Linear Embedding.