Date 
Topic 
Speaker 
February 22 
A Nearlinear Time epsApproximation Algorithm for Geometric Bipartite Matching
Abstract:
For ddimensional point sets A,B, A = B = n, and a parameter \eps > 0, we present an algorithm that computes, in nearlinear 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_pnorm using a distance function d(.,.) based on a randomly shifted quadtree. Our algorithm iteratively generates an approximate minimumcost 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 nearlinear running time of the algorithm.
Joint work with Pankaj Agarwal. (To Appear in STOC'12)

Sharathkumar Raghvendra 
March 7 
Spring Break
Spring break (also known as March break, study week, reading week or the Easter holidays in the United Kingdom and some parts of Canada) is a recess in early spring at universities and schools in the United States, Canada, China, Korea, Japan, Taiwan, Mexico, the United Kingdom, and other countries.

404 Speaker Not Found 
March 14 
Computing Optimal Security Strategies in Networked Domains: A CostBenefit Approach
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 twofold. 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.

Josh Letchford 
March 22 
NearestNeighbor Searching Under Uncertainty
RIP Final and Masters: Wuzhou Zhang
Date: Thursday, March 22, 2012
Time: 1:002:30 PM
Place: LSRC D344
Committee: Pankaj K. Agarwal (advisor), Kamesh Munagala, Jun Yang
Abstract:
Nearestneighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an epsapproximate ENN, for a given error parameter eps > 0, under different distance functions. These methods build an index of nearlinear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or epsapproximate ENN queries with provable performance guarantees.
Joint work with Pankaj K. Agarwal, Alon Efrat, and Swaminathan Sankararaman. To appear in PODS 2012.
http://www.cs.duke.edu/events/?id=00000001469

Wuzhou Zhang 
April 4 
The multiplicative weights update method: a meta algorithm and applications
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.

Sayan Bhattacharya 
April 11 
Geometric algorithms for structure determination of proteins from uncertain restraints
Abstract:
Nuclear magnetic resonance (NMR) spectroscopy is a primary tool to
perform structural studies of proteins in physiologicallyrelevant
solution conditions. Restraints on distances between pairs of protons
in the protein, derived from the nuclear Overhauser effect (NOE),
provide information about the structure of the protein in its folded
state. Ambiguity in the proton assignments for the NOEs render these
geometric constraints uncertain, hence complicating the determination
of an atomicresolution structure. In cases where this uncertainty is
unable to be resolved experimentally, computational approaches are
needed, but traditional solutions often rely on stochastic search
coupled with simulation, which has many tunable parameters that must
be chosen carefully and can potentially miss structures consistent
with the experimental restraints. We reduce the structure
determination of protein homooligomers with cyclic symmetry to
computing geometric arrangements of unions of annuli in a plane. Our
algorithm, DISCO, runs in expected O(n^2) time, where n is the number
of distance restraints, allowing for ambiguous assignments.
Furthermore, DISCO guarantees to report all oligomeric structures
consistent with the experimental restraints. DISCO's implementation
uses the arrangements package in CGAL and is freely available as open
source software.
In the second half of the talk, I will present recent work on protein
backbone structure determination from uncertain restraints on covalent
bond orientation. Using a parametric model of protein backbone
flexibility, the problem of finding protein conformations that satisfy
the restraints can be modeled using geometric arrangements of curves
on a sphere. Using the arrangements, we then seek to conservatively
compute all satisfying parameters of the flexibility model. These
parameters then describe all conformations of the protein consistent
with the restraints.

Jeff Martin 
April 16 
Describable Visual Attributes for Faces
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
attributebased 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 realworld 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 coadvised 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 realworld 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.

Neeraj Kumar 
April 18 
Processing a Large Number of Continuous Preference Topk Queries
Abstract:
Given a set of objects, each with multiple numeric attributes, a
(preference) topk query retrieves the k objects with the highest
scores according to a user preference, defined as a linear combination
of attribute values. We consider the problem of processing a
large number of continuous topk queries, each with its own preference.
When objects or user preferences change, the query results
must be updated. We present a dynamic index that supports the
reverse topk query, which is of independent interest. Combining
this index with another one for topk queries, we develop a scalable
solution for processing many continuous topk queries that exploits
the clusteredness in user preferences. We also define an approximate
version of the problem and present a solution significantly
more efficient than the exact one with little loss in accuracy.

Albert Yu 
April 25 
Estimating Geodesic Distances via Persistent Homology, with Applications to Dimension Reduction
Abstract:
Given a point cloud X sampled from or near a Riemannian manifold M
embedded in highdimensional 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 nonlinear dimension reduction techniques, including IsoMap
and Locally Linear Embedding.

Paul Bendich 
May 2 
Semialgebraic range searching
Abstract:
Let P be a set of $n$ points in dspace We present a linearsize data structure for answering range queries on P with constantcomplexity semialgebraic sets in time close to O(n^{11/d}), essentially matching the performance of similar structures for simplex range searching, and significantly improving earlier solutions for d > 3. This almost settles a longstanding open problem in range searching.
Joint work with Jiri Matousek and Micha Sharir.

Pankaj K. Agarwal 