Select a calendar:
Filter February Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for February 28, 2008
-
CS Colloq: Internet Equilibrium Analysis Through Separation of User and Network Behavior
Thu, Feb 28, 2008 @ 11:00 AM - 12:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Internet Equilibrium Analysis Through Separation of User and Network
BehaviorSpeaker: Prof. Y.C. Tay (National University of Singapore)ABSTRACT:
Internet complexity makes reasoning about traffic equilibrium difficult, partly
because users react to congestion. This difficulty calls for an analytic
technique that is simple, yet have enough details to capture user behavior and
flexibly address a broad range of
issues.This talk presents such a technique. It treats traffic equilibrium as a balance
between an inflow controlled by user demand, and an outflow provided by network
supply (link capacity, congestion avoidance, etc.). This decomposition is
demonstrated with a surfing session model, and validated with a traffic trace
and NS2 simulations.The technique's accessibility and breadth are illustrated through an analysis
of several issues concerning the location, stability, robustness and dynamics
of traffic equilibrium.(Joint work with D. Nguyen Tran, Eric Y. Liu, Wei Tsang Ooi and Robert Morris)BIO:
Y.C. Tay received his B.Sc. degree from the University of Singapore and Ph.D.
degree from Harvard University. He is a professor in the Departments of
Mathematics and Computer Science at the National University of Singapore
(http://www.comp.nus.edu.sg/~tayyc). His main research interest is performance
modeling.Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloq: Fitting Polynomials to Noisy Data
Thu, Feb 28, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Fitting Polynomials to Noisy DataSpeaker: Dr. Parikshit Gopalan (Washington)ABSTRACT:
The problem of finding the polynomial that best fits a noisy data-set (or
polynomial reconstruction) has a long history, dating back to curve-fitting
problems studied in the 1800s. In the last two decades, there has been
tremendous progress on this problem in computer science, driven by the
discovery of powerful new algorithms. These results have spurred exciting new
developments in Coding theory, Computational learning, Cryptography and
Hardness of Approximation. In this talk, we will explore this problem from the
perspectives of Coding theory and Computational learning.We begin with an algorithm for decoding a well-studied family of binary
error-correcting codes called Reed-Muller codes, which are obtained from
low-degree polynomials. The salient feature of this algorithm is that it works
even when the number of errors far exceeds the so-called Johnson bound.I will present an algorithm for agnostically learning decision trees under the
uniform distribution. This is the first polynomial time algorithm for learning
decision trees in a harsh noise model. This algorithm solves the
reconstruction problem for real polynomials using tools from convex
optimization.I will also discuss settings where the reconstruction problem seems
intractable. We will see evidence that the notorious Noisy Parity problem is
hard under the uniform distribution. We will see hardness results suggesting
that learning simple concepts with noise is impossible for arbitrary
distributions.BIO:
Parikshit Gopalan grew up in India in the city of Bombay (now called Mumbai).
He graduated with an undergraduate degree from IIT-Bombay (whose name,
thankfully, has not changed). He received his Ph.D from Georgia Tech in August
2006, under the guidance of Dick Lipton. Following this, he did a short stint
as a postdoctoral researcher at the University of Texas at Austin. He is
currently a postdoc at the University of Washington, visiting Princeton
University.His research focuses on theoretical computer science, especially on algebraic
problems arising from algorithms and complexity. He also likes to dabble in
other areas such as Data-stream algorithms and Communication complexity.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
