|
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. |
|
