Conferences, Lectures, & Seminars
Events for January
-
CS Colloquia: Bertrand Competition in Networks
Thu, Jan 17, 2008 @ 11:00 AM - 12:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Bertrand Competition in NetworksSpeaker: Prof. Shuchi Chawla (Wisconsin)ABSTRACT:
The Internet is a unique modern artifact given its sheer size and the
number of its users. Given its continuing distributed and ad-hoc
evolution, there have been growing concerns about the effectiveness of
its current routing protocols in finding good routes and ensuring
quality of service. Imposing congestion-based and QoS-based prices on
traffic has been suggested as a way of combating the ills of this
distributed growth and selfish use of resources. Unfortunately, the
effectiveness of such approaches relies on the cooperation of the
multiple entities implementing them, namely the ISPs or Internet
service providers. The goals of the ISPs do not necessarily align with
the social objectives of efficiency and quality of service; their
primary objective is to maximize their own profit. It is therefore
imperative to study the following question: given a large
combinatorial market such as the Internet, suppose that the owners of
resources selfishly price their product to maximize their own profit,
and consumers selfishly purchase resources to maximize their own
utility, how does this effect the functioning of the market as a
whole?We study this problem in the context of a simple network pricing game,
and analyze the performance of equilibria arising in this game as a
function of the degree of competition in the game, the network
topology, and the demand structure. Economists have traditionally
studied such questions in single-item markets. It is well known, for
example, that monopolies cause inefficiency in a market by charging
high prices, whereas competition has the effect of driving prices down
and operating efficiently. Our work extends the classical Bertrand
model of competition from economics to the network setting. For
example, we ask: is competition in a network enough to ensure
efficient operation? does performance worsen as the number of
monopolies grows? does the answer depend in an interesting way on the
network topology and/or demand distribution? We provide tight bounds
on the performance (efficiency) of the network.This is joint work with Tim Roughgarden.BIO:
Shuchi Chawla is an assistant professor of Computer Science at
University of Wisconsin - Madison. She received her PhD in 2005 from
Carnegie Mellon University and her Bachelor of Technology degree from
the Indian Institute of Technology, Delhi, India in 2000. Her research
interests lie in theoretical computer science, with emphasis towards
approximation algorithms, combinatorial optimization, and game theory.
Shuchi is the recepient of an NSF CAREER award and an IBM Ph.D.
fellowship.Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloquia: Network Resilience to Attack and Disaster
Thu, Jan 17, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Network Resilience to Attack and DisasterSpeaker: Prof. Dan Rubenstein (Columbia)ABSTRACT:
Traditional network design can compensate for a small number of node
and link failures, but cannot handle attacks or failures on a massive
scale. These massive-scale phenomena may be due to malicious behavior
in the network, such as a denial of service attack, or due to
disaster, such as an emergency sensor network deployed in a
catastrophic location such as a fire or flood. A primary focus of our
research has been to design or enhance routing protocols so that they
are more resilient to these massive-scale challenges. The talk will
first cover the Secure Overlay Services (SOS) architecture we proposed
that utilizes network overlays to proactively protect targeted
Internet sites from distributed denial of service (DDoS) attacks.
Next, we will explore the problem of maximizing the amount of data
that can be extracted to a base-station from a sensor network whose
nodes are undergoing rapid failures. We develop a novel distributed
network coding technique and demonstrate how, in a massive failure
setting, our coding/routing technique outperforms prior state-of-the-art. I
will finish the talk with a brief run-through of other projects that
our lab has focused on.BIO:
Dan Rubenstein is an Associate Professor of Electrical Engineering and
Computer Science at Columbia University. He received a B.S. degree in
mathematics from M.I.T., an M.A. in math from UCLA, and a PhD in computer
science from University of Massachusetts, Amherst. His research interests are
in network technologies, applications, and performance analysis, with a
substantial emphasis on resilient and secure networking, distributed
communication algorithms, and overlay technologies. He has received an NSF
CAREER Award, an IBM Faculty Award, the Best Student Paper award from the ACM
SIGMETRICS 2000 conference, and a Best Paper award from the IEEE ICNP 2003
Conference.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloquia: Social Robots
Tue, Jan 22, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Social RobotsSpeaker: Prof. Reid Simmons (CMU)ABSTRACT:
As robots become more ubiquitous in society, they will have to learn to
interact with people in socially acceptable ways. For the past six years,we
have been developing techniques that enable robots to behave according to
social conventions, both conversationally and spatially. The techniquesinvolve
explicit modeling of human behavior and social conventions,probabilistic
reasoning about situations and the intentions of people, and explicit
representation of affect and mutual interaction. We have developed several
robots that embody these ideas, including GRACE, a robot that attended the
National Conference on Artificial Intelligence, the roboceptionist, a joint
project with the School of Drama, and a robot that dances rhythmically with
children. This talk will describe our efforts in this area, focusing on the
techniques that we have developed and highlighting the gap that still remains
between the behavior of our robotsand true social interaction.BIO:
Reid Simmons is a Research Professor in the School of Computer Science at
Carnegie Mellon University. He earned his B.A. degree in 1979 in
ComputerScience from SUNY at Buffalo, and his M.S. and Ph.D. degrees from MIT
in 1983 and 1988, respectively, in the field of Artificial Intelligence. Since
coming to Carnegie Mellon in 1988, Dr. Simmons' research has focusedon
developing self-reliant robots that can autonomously operate over extended
periods of time in unknown, unstructured environments. This work involves
issues of robot control architectures, probabilistic planning and reasoning,
monitoring and fault detection, and robust indoor and outdoornavigation. More
recently, Dr. Simmons has focused on the areas of human-robot social
interaction, coordination of multiple heterogeneous robots, and formal
verification of autonomous systems. Over the years, he has been involved in the
development of over a dozen autonomous robots.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloquium - Reid Simmons
Tue, Jan 22, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
TITLE:
Social Robots ABSTRACT:
As robots become more ubiquitous in society, they will have to learn to interact with people in socially acceptable ways. For the past six years,we have been developing techniques that enable robots to behave according to social conventions, both conversationally and spatially. The techniquesinvolve explicit modeling of human behavior and social conventions,probabilistic reasoning about situations and the intentions of people, and explicit representation of affect and mutual interaction. We have developed several robots that embody these ideas, including GRACE, a robot that attended the National Conference on Artificial Intelligence, the roboceptionist, a joint project with the School of Drama, and a robot that dances rhythmically with children. This talk will describe our efforts in this area, focusing on the techniques that we have developed and highlighting the gap that still remains between the behavior of our robotsand true social interaction. BIOGRAPHY:
Reid Simmons is a Research Professor in the School of Computer Science at Carnegie Mellon University. He earned his B.A. degree in 1979 in ComputerScience from SUNY at Buffalo, and his M.S. and Ph.D. degrees from MIT in 1983 and 1988, respectively, in the field of Artificial Intelligence. Since coming to Carnegie Mellon in 1988, Dr. Simmons' research has focusedon developing self-reliant robots that can autonomously operate over extended periods of time in unknown, unstructured environments. This work involves issues of robot control architectures, probabilistic planning and reasoning, monitoring and fault detection, and robust indoor and outdoornavigation. More recently, Dr. Simmons has focused on the areas of human-robot social interaction, coordination of multiple heterogeneous robots, and formal verification of autonomous systems. Over the years, he has been involved in the development of over a dozen autonomous robots.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Webmaster
-
CS Colloquia: Approximation algorithms for combinatorial allocation problems
Tue, Jan 29, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Approximation algorithms for combinatorial allocation problemsSpeaker: Dr. Jan Vondrak (Princeton)ABSTRACT:
Combinatorial allocation problems arise in situations where a set of items
should be distributed among n players in order to maximize a certain social
utility function. Such problems have been subject to recent interest due to
their applications in combinatorial auctions and electronic commerce. Since
allocation problems are typically NP-hard to solve optimally, we seek
approximation algorithms that find a solution of value at least c * OPT where
OPT is the optimum and cA particular case of interest is the Submodular Welfare Problem where utility
functions are assumed to be monotone and submodular. It has been known since
1978 that a greedy algorithm gives a 1/2-approximation [Nemhauser, Wolsey,
Fisher] for a more general problem of submodular maximization subject to a
matroid constraint. I will show how this can be improved to a
(1-1/e)-approximation - an approximation factor which is known to be optimal.
A new technique that we use is the approximate solution of a non-linear
optimization problem using a "continuous greedy algorithm".(partly joint work with G. Calinescu, C. Chekuri and M. Pal)BIO:
I grew up in the Czech republic and I got a Master's degree in computer
science from Charles University in Prague. Then I went to grad school at MIT
where I got a PhD in applied math in 2005. My advisor was Michel Goemans. I
spent a year as a postdoc at Microsoft Reserch (2005-06) and currently I'm a
postdoc at Princeton University.
~Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
Approximation algorithms for combinatorial allocation problems
Tue, Jan 29, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
ABSTRACT:
Combinatorial allocation problems arise in situations where a set of items should be distributed among n players in order to maximize a certain social utility function. Such problems have been subject to recent interest due to their applications in combinatorial auctions and electronic commerce. Since allocation problems are typically NP-hard to solve optimally, we seek approximation algorithms that find a solution of value at least c * OPT where OPT is the optimum and cA particular case of interest is the Submodular Welfare Problem where utility functions are assumed to be monotone and submodular. It has been known since
1978 that a greedy algorithm gives a 1/2-approximation [Nemhauser, Wolsey, Fisher] for a more general problem of submodular maximization subject to a matroid constraint. I will show how this can be improved to a (1-1/e)-approximation - an approximation factor which is known to be optimal.
A new technique that we use is the approximate solution of a non-linear optimization problem using a "continuous greedy algorithm".(partly joint work with G. Calinescu, C. Chekuri and M. Pal)BIO:
I grew up in the Czech republic and I got a Master's degree in computer science from Charles University in Prague. Then I went to grad school at MIT where I got a PhD in applied math in 2005. My advisor was Michel Goemans. I spent a year as a postdoc at Microsoft Reserch (2005-06) and currently I'm a postdoc at Princeton University.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
Mitigating Attacks in Unstructured Multicast Overlay Networks
Wed, Jan 30, 2008 @ 02:00 PM - 03:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Abstract:Many multicast overlay networks maintain application-specific performance goals by dynamically adapting the overlay structure when the monitored performance becomes inadequate. This adaptation results in an unstructured overlay where no neighbor selection constraints are imposed. Although such networks provide resilience to benign failures, they are susceptible to attacks conducted by adversaries that compromise overlay nodes. Previous defense solutions proposed to address attacks against overlay networks rely on strong organizational constraints and are not effective for unstructured overlays.We identify, demonstrate and mitigate insider attacks against measurement-based adaptation mechanisms in unstructured multicast overlay networks. We propose techniques to decrease the number of incorrect adaptations by using outlier detection and limit the impact of malicious nodes by aggregating local information to derive global reputation for each node. We demonstrate the attacks and mitigation techniques through Internet deployments of a mature overlay multicast system.In addition, we also show how the mitigation techniques we have developed effectively improve the resilience of virtual coordinate systems. Virtual coordinate systems allow hosts on the Internet to determine the latency to arbitrary hosts without actively monitoring all nodes in the network and are used to optimize overlay construction and maintenance. We demonstrate the attacks and mitigation techniques in the context of a well-known distributed virtual coordinate system using simulations based on three representative, real-life Internet topologies of hosts and corresponding round trip times (RTT).Bio:Cristina Nita-Rotaru is an Assistant Professor in the Department of Computer Science at Purdue University where she established the Dependable and Secure Distributed Systems Laboratory. Her research interests lie in designing distributed systems, network protocols and applications that are dependable and secure, while maintaining acceptable levels of performance. Current research focuses on: designing intrusion-tolerant architectures for distributed services that scale to wide-area networks, studying attacks and defenses in overlay networks, investigating survivable routing in wireless ad hoc networks, and designing group services for wireless mesh networks.Cristina Nita-Rotaru is a recipient of the NSF Career Award in 2006 and a recipient of the Purdue Teaching for Tomorrow Award in 2007. She has served on the Technical Program Committee of numerous conferences in security, dependability, networking and distributed systems. Her work is funded by the Center for Education and Research in Information Security and Assurance (CERIAS), by the Defense Advanced Research Projects Agency (DARPA), and by the National Science Foundation (NSF).
Location: USC-ISI, Marina del Rey, CA 90292, 111th Fl.,POC: Joe Kemp (310) 448.9171
Audiences: Everyone Is Invited
Contact: CS Front Desk
