This Week's CS Seminars

Tuesday, April 29, 10:30AM, CSEB B17; Dina Papagiannaki, Intel Research; Self-Organization in High Density 802.11 Wireless Access Networks

Date & Time: Tuesday, April 17, 2008 @ 10:30 am - 12:00
Location: CSEB B17

Title: Self-Organization in High Density 802.11 Wireless Access Networks

Abstract:
The increased popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. Such high density leads to sub-optimal performance unless the interfering networks learn how to optimally share the spectrum. In this talk I will describe three distributed algorithms that allow (i) multiple interfering 802.11 WLANs to select their operating frequency in a way that minimizes global interference, (ii) clients to choose their Access Point so that the bandwidth of all interfering networks is shared optimally, (iii) APs and clients to select their transmission power and Clear Channel Assessment (CCA) threshold so as to maximize the overall network capacity. All algorithms fall into a unified framework based on Gibbs sampling and optimize global network performance based on local information. They do not require explicit coordination among the wireless devices, and can thus operate in diverse cooperative environments with no single administrative authority. We study implementation requirements and show that significant benefits can be gained using a prototype implementation on the Intel 2915 ABG wireless network interface cards.

Bio:
Konstantina (Dina) Papagiannaki received her first degree in electrical and computer engineering from the National Technical University of Athens, Greece, in 1998, and her PhD degree from the University College London, U.K., in 2003. From 2000 to 2004, she was a member of the IP research group at the Sprint Advanced Technology Laboratories. She is currently with Intel Research in Pittsburgh, after 3 years at Intel Research in Cambridge, UK.
Her research interests are in Internet measurements, modeling of Internet traffic, security, network design and planning, and infrastructure wireless networks.

Thursday May 1, 10:30 AM, CSEB B17; Petros Drineas, Rensselaer Polytechnic University; Randomized Algorithms for Matrix Computations and Applications to Data Mining

Date & Time: Thursday, April 24, 2008 @ 10:30 am - 12:00 pm
Location: CSEB B17

Title: Randomized Algorithms for Matrix Computations and Applications to Data Mining

Abstract:
The introduction of randomization in the design and analysis of algorithms for matrix computations (such as matrix multiplication, least-squares regression, the Singular Value Decomposition (SVD), etc.) over the last decade provided a new paradigm and a complementary perspective to traditional numerical linear algebra approaches. These novel approaches were motivated by technological developments in many areas of scientific research that permit the automatic generation of large data sets, which are often modeled as matrices.

In this talk we will focus on the Singular Value Decomposition (SVD) of matrices and the related Principal Components Analysis, which have found numerous applications in extracting structure from datasets in diverse domains, ranging from the social sciences and the internet to biology and medicine. The extracted structure is expressed in terms of singular vectors, which are linear combinations of all the input data and lack an intuitive physical interpretation. We shall discuss matrix decompositions which express the structure in a matrix as linear combination of actual columns (or rows) of the matrix. Such decompositions are easier to interpret in applications, since the selected columns and rows are subsets of the data. Our (randomized) algorithms run in cubic time and come with strong accuracy guarantees. Finally, we will demonstrate how these decompositions may be applied in order to identify ancestry-informative DNA markers that may be used to assign individuals to populations of origin.

Bio:
Prof. Drineas is an assistant professor in the Computer Science Department of Rensselaer Polytechnic Institute, which he joined in 2003. Prof. Drineas earned a doctorate in computer science from Yale University in 2003 and a bachelor in computer engineering from the University of Patras, Greece, in 1997. His research interests lie in the area of the design and analysis of algorithms, and in particular the design and analysis of randomized algorithms for linear algebraic problems. Prof. Drineas is the recipient of an NSF CAREER award.