|
| |
|
Seminar Dates for
Spring 2008: |
|
|
|
|
An Improved
Approximation Algorithm for the Column Subset Selection Problem by
Christos Boutsidis |
02/13/08 |
|
Abstract |
|
|
Sampling algorithms
and Coresets for Regression and Applications by Michael W.
Mahoney |
03/26/08 |
|
Abstract: L2
regression, also known as the least squares approximation problem, and
more generally Lp regression, are fundamental problems that have
numerous
applications in mathematics, computer science, and statistical data
analysis. Recall that the over-constrained Lp regression problem takes
as
input an n x d matrix A, where n > d, an n-vector b, and a number p, and
it
returns as output a d-vector x such that ||Ax-b||_p is minimized.
Several
randomized algorithms for this problem, each of which provides a
relative-error approximation to the exact solution, are described. The
first algorithm applies novel ``subspace sampling'' probabilities to
randomly sample constraints and thus construct a coreset for the L2
regression problem. The second algorithm applies a random preprocessing
before the sampling step and uses a ''fast'' version of the
Johnson-Lindenstrauss lemma to obtain an efficient approximation to the
L2
regression problem. The third algorithm generalizes the concept of a
''well-conditioned'' basis and of ''subspace-preserving sampling'' to
obtain
efficiently a coreset for Lp regression. Applications of these
algorithms
to internet data analysis will be briefly discussed. |
|
|
Computer Science in the Information Age by John Hopcroft |
04/03/08 |
| The
last forty years have seen computer science evolve as a major academic
discipline. Today the field is undergoing a major change. Some of the
drivers of this change are the internet, the world wide web, large
sensor networks, large quantities of information in digital form and the
wide spread use of computers for accessing information. This change is
requiring universities to revise the content of computer science
programs. This talk will cover the changes in the theoretical
foundations needed to support information access in the coming years. |
Location: Troy 2018 Time: 4:00 p.m. |
| The
Role of Information in the Cop Robber Game by
Nikhil Karnad |
04/09/08 |
| In the
first part of the talk, I present our work on the cop-robber game played
in turns on a graph. A graph G is called cop-win if a single cop can
capture (coincide with) a robber on G. It is usually assumed that the
players can "see" each other at all times. We study the effect of
reducing the visibility of the cop and present results on cop-win
graphs. The second part of the talk focuses on work motivated by
monocular vision systems used in robotics applications. We study a
variant of the Lion-and-Man game in which the pursuer (lion) is able to
gather bearing-only information on the evader (man). We present results
on how this restricted sensing model affects the game. |
|
|
Disjoint Paths in Networks by Sanjeev Khanna |
04/16/08 |
| Abstract: A fundamental problem in combinatorial optimization is the
edge-disjoint paths problem (EDP). We are given a network and a
collection of source-destination pairs in the network. The goal is to
maximize the number of pairs that can be connected by edge-disjoint
paths. Even special cases of EDP correspond to non-trivial optimization
problems, and the problem becomes NP-hard in very restricted settings.
In this talk, we will survey some recent progress on understanding the
approximability threshold of EDP and its variants. While the recent
developments have essentially resolved the approximability of EDP and
related problems in directed graphs, the status of the undirected case
remains wide open. We will describe a promising framework for getting
much improved algorithms for undirected EDP when some congestion is
allowed. In particular, we will highlight a conjecture whose resolution
is strongly tied to the approximability of the undirected case, and
describe some results that lend support to this conjecture.
|
Location: Sage 3510 Time: 4:00 p.m.
|
|
Epidemiology and Graph Cuts by Elliot Anshelevich |
04/30/08 |
| The
connection between epidemiology and graph cuts leads to many new
problems that are both important and interesting. Specifically, we
consider the question of immunizing a few individuals in a social
network in order to stop or slow the process of an epidemic. We give a
short overview of known results in this area, and point out fundamental
problems that are still open. For example, given a graph, a set of
infected nodes, and transmission probabilities on edges, no good
algorithms currently exist for finding the nodes to "immunize" in order
to save as many lives as possible. |
|
| The
Spectral Gap of a Graph by Paul Horn |
05/07/08 |
| The
spectrum of a graph allows great insight on many important graph
properties; among them discrepancy, expansion and the mixing time of
random walks. An advantage of looking at the spectrum is that it can, in
fact, be computed efficiently and allows us a way of guaranteeing
expansion (which in general is NP-hard to compute). In this talk, we
discuss various graph spectra and their uses and then focus on the
spectrum of a normalized Laplacian whose spectrum captures information
about graphs which have arbitrary degree sequences. We establish bounds
showing that the spectral gap of a random subgraph of a graph is close
to that of the original graph. We then turn to the question of how
'good' can the spectral gap of a graph be, giving an answer which
generalizes a classical theorem of Alon and Boppana for regular graphs
to graphs with an arbitrary degree sequence. Some of this work is joint
work with Fan Chung. |
|
|
|
Fall 2007 Seminar
Dates: |
|
|
|
|
Terminal
Backup, 3D Matching and Covering Cubic Graphs by Elliot
Anshelevich |
09/05/07 |
|
We define a
problem called Simplex Matching, and show that it is solvable in
polynomial time. While Simplex Matching is interesting in its own
right as a nontrivial extension of non-bipartite min-cost matching,
its main value lies in many (seemingly very different) problems that
can be solved using our algorithm. For example, suppose that we are
given a graph with terminal nodes, non-terminal nodes, and edge
costs. Then, the Terminal Backup problem, which consists of finding
the cheapest forest connecting every terminal to at least one other
terminal, is reducible to Simplex Matching. Simplex Matching is also
useful for various tasks that involve forming groups of at least 2
members, such as project assignment and variants of facility
location. In an instance of Simplex Matching, we are given a
hypergraph H with edge costs, and edge size at most 3. We show how
to find the min-cost perfect matching of H efficiently, if the edge
costs obey a simple and realistic inequality that we call the
Simplex Condition. The algorithm we provide is relatively simple to
understand and implement, but difficult to prove correct. In the
process of this proof we show some powerful new results about
covering cubic graphs with simple combinatorial objects. |
|
Optimal Oblivious Routing Using Metric
Embeddings by Malik Magdon Ismail |
09/12/07 |
|
In
oblivious routing the packet paths must be constructed independently
of each other. Such algorithms are distributed and scalable. We give
a simple oblivious routing algorithm for geometric networks in which
the nodes are embedded in the Euclidean plane. In our algorithm, a
packet path is constructed by first choosing a random intermediate
node in the space between the source and destination, and then the
packet is sent to its destination through the intermediate node. We
analyze the performance of the algorithm in terms of the stretch and
congestion of the resulting paths. The challenge is to obtain
constant stretch, and near optimal congestion. We show that for well
embeded networks, this is possible, giving the first result to
control both stretch and congestion in a general class of networks.
We give applications of our general result to the mesh topology and
uniformly distributed disc graphs. Previous oblivious routing
algorithms with near optimal congestion use many intermediate nodes
and do not control the stretch. |
|
|
Locality model for
the evolution of social networks by Konstantin Mertsalov |
09/19/07 |
We
propose the model of a dynamic social network that is based on the
principle of local communication. In this model participants of the
network communicate strictly with the members of it's local area.
We study the different ways of selecting the local area of a
participant and different rules for link creation with in the area
and propose the final model based on this. We also propose the
testing methodology for the dynamic model. We present the result of
an application of this model to simulation of the communication in
the Blogosphere.
|
|
|
No seminar this
week (DIMACS workshop) |
09/26/07 |
|
From shortest
paths to quasi-concave minimization by Evdokia Nikolova |
10/03/07 |
In
this talk I will walk through a journey of research, that started
with a simple application in mind: that of finding the shortest path
in an uncertain environment (or: how to get to the airport
ontime).In particular, our goal was to maximize the probability that
the path length does not exceed a given threshold value (deadline).
This stochastic shortest path problem is one of few that have
considered a nonlinear objective function--due to the difficulty of
finding closed-form expressions for the objective, in addition to
the challenge of optimizing the objective, which falls in the
category of non-convex optimization. We give a surprising exact
$n^{\Theta(\log n)}$ algorithm for the case of independent normally
distributed edge lengths, which is based on quasi-concave
minimization.
Motivated by the stochastic shortest path problem, we further embark
on giving new tools for quasi-concave minimization--a problem of
considerable difficulty, whose solutions are usually exponential,
and typically heuristics of unknown approximation guarantees are
employeed. To that effect, we provide the first smoothed analysis of
quasi-concave minimization. The analysis is based on a smoothed
bound for the number of extreme points of the projection of the
feasible polytope onto a $k$-dimensional subspace. The bound we
derive can be used to design a polynomial-time approximation
algorithm for low-rank quasi-concave minimization, as is the case of
the shortest path problem above. We supplement the positive smoothed
bound with a hardness result that general quasi-concave minimization
is hard to approximate. The latter implies that our bound is tight,
in that no polynomial bound is possible for general quasi-concave
minimization. |
|
| No
seminar this week |
10/10/07 |
|
Optimal Oblivious Routing Using Metric
Embeddings by Malik Magdon Ismail(cont.) |
10/17/07 |
| In
oblivious routing the packet paths must be constructed independently
of each other. Such algorithms are distributed and scalable. We give
a simple oblivious routing algorithm for geometric networks in which
the nodes are embedded in the Euclidean plane. In our algorithm, a
packet path is constructed by first choosing a random intermediate
node in the space between the source and destination, and then the
packet is sent to its destination through the intermediate node. We
analyze the performance of the algorithm in terms of the stretch and
congestion of the resulting paths. The challenge is to obtain
constant stretch, and near optimal congestion. We show that for well
embeded networks, this is possible, giving the first result to
control both stretch and congestion in a general class of networks.
We give applications of our general result to the mesh topology and
uniformly distributed disc graphs. Previous oblivious routing
algorithms with near optimal congestion use many intermediate nodes
and do not control the stretch. |
|
| No
seminar this week (FOCS) |
10/24/07 |
|
Condorcet winner probabilities and
Voting Procedure by Mukkai Krishnamoorthy |
10/31/07 |
|
Condorcet voting scheme chooses a winning candidate as one who
defeats all others in pairwise majority rule. We provide a review
which includes the rigorous mathematical treatment for calculating
the limiting probability of a Condorcet winner for any number of
candidates and value of $n$ odd or even and with arbitrary ran k
order probabilities, when the voters are independent. We provide a
compact and complete Table for the limiting probability of a
Condorcet winner with three candidates and arbitrary rank order
probabilities. We present a simple proof of a result of May to show
the limiting probability of a Condorcet winner tends to zero as the
number of candidates tends to infinity. We show for the first time
that the limiting probability of a Condorcet winner for any given
number of candidates $m$ is monotone decreasing in $m$ for the
equally likely case. This, in turn, settles the conjectures of Kelly
and Buckley and Westen for the case $n o infty$. We prove the
validity of Gillett's conjecture on the minimum value of the
probability of a Condorcet winner for $m=3$ and any $n$. We
generalize this result for any $m$ and $n$ and obtain the minimum
solution and the minimum probability of a Condorcet winner. |
|
Clusters in a multigraph with elevated density by Mark
Goldberg |
11/07/07 |
We
will discuss the edge-coloring problem for multigraphs, and present
an old conjecture which connects the chromatic index $\chi'$ of a
multigraph with its density $\Gamma$ and maximal vertex degree
$\Delta$. We show that
(a) two well-known lower bounds for the chromatic index of a
multigraph are identical;
(b) for multigraphs with $\Gamma > \Delta +1$, the size of any
cluster (a subset of vertices with an integrally
maximal density) is bounded from the above by a function, which
depends on $\Delta$ and $\Gamma$ only;
(c) for every multigraph with $\Gamma > \Delta$ the collection of
minimal clusters is cycle-free. |
|
|
The Border Gateway Protocol (BGP) and Generalizations by
Gordon Wilfong |
11/15/07 |
|
The Border Gateway Protocol (BGP) is the interdomain routing
protocol used by routers to exchange routing information in the
Internet. While intradomain protocols such as RIP can be viewed as
distributed algorithms for computing shortest paths, BGP is actually
trying to solve a problem we call the Stable Paths Problem (SPP).
Most of the talk will be in terms of SPP to allow us to mask the
complex details of how BGP operates. We will discuss a number of
decision questions concerning BGP convergence and show that they are
NP-hard. Then we'll consider modifications to the protocol and
configuration constraints that guarantee convergence. A fractional
multi-path version of SPP is discussed and we show that this problem
always has a stable solution. This leads to open problems such as
how to design a protocol (i.e., a distributed algorithm) to achieve
such a fractional stable solution. Some optimization questions
arising from multi-path routing will also be discussed. |
Thursday, November 15, 4:00 p.m.
Location: AE 214 |
| No
seminar this week (Thanksgiving) |
11/21/07 |
|
Price of Stability of Survivable Connection Game by Bugra
Caskurlu |
11/28/07 |
| We
study the survivable version of the game theoretic network formation
model known as the Connection Game, originally introduced in STOC'03
by Anshelevich, Dasgupta, Tardos and Wexler. In this model, players
attempt to connect certain pairs of nodes in a network by purchasing
edges, and sharing their costs with other players. We introduce the
survivable version of this game, where each player desires r
edge-disjoint connections between her pair of nodes, instead of just
a single connecting path. For the single-source version of this
game, if a player is only allowed to deviate by changing the
payments on one of her connection paths at a time, instead of all of
them at once, we prove that the price of stability is 1,
i.e., there always exists a stable solution that is as good as the
centralized optimum. This can model the case where a player wishes
to keep most of her paths the same as before the deviation, the case
where a complex deviation involving re-routing of all the player
paths is too much for a player, or the case where each path of a
single player is managed by a different entity, which is extremely
possible when a player represents a large company. For the general
case, where players are allowed to change the payments on all their
paths at once, we show that there always exists an r-approximate
Nash equilibrium that is as good as the centralized optimum, and
provide lower bounds for the price of stability. |
|
|
The Rank Aggregation Problem by
David Williamson |
12/05/07 |
|
The rank aggregation problem was introduced by Dwork, Kumar, Naor,
and Sivakumar (WWW 2001) in the context of finding good rankings of
web pages by drawing on multiple input rankings from various search
engines. The work draws on earlier work in the social choice
literature on combining voter preferences specified by ranked
alternatives. Dwork et al. propose finding a ranking that minimizes
the sum of its Kendall distance to the input rankings; this can be
viewed as a weighted feedback arc set problem. I will give an
overview of the rank aggregation problem and some of its
applications, including an application to intranet search (WWW
2003). I will also cover recent work done on finding good
approximation algorithms for the problem. In particular, Ailon,
Charikar, and Newman (STOC 2005) introduce a randomized ``pivoting''
algorithm for rank aggregation and related problems; recent work has
extended this to deterministic pivoting algorithms for constrained
versions of the problem (van Zuylen, Hegde, Jain and Williamson,
SODA 2007, van Zuylen and Williamson 2007) and has yielded a
polynomial-time approximation scheme for the problem (Kenyon-Mathieu
and Schudy, STOC 2007). If time permits, I will discuss some
extensions of this work to finding good clusterings and hierarchical
clusterings. |
Wednesday, December 5, 4:00 p.m.
Location: Ricketts 211 |
|
|
|
|
