Select a calendar:
Filter April Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Conferences, Lectures, & Seminars
Events for April
-
CS Colloquium
Tue, Apr 05, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Minlan Yu, Princeton University
Talk Title: Scalable Management of Enterprise and Data Center Networks
Abstract: The networks in campuses, companies, and data centers are growing larger and becoming more complicated to manage. Today, network operators devote tremendous time and effort to various management tasks such as customized routing, access control, and troubleshooting. Rather than trying to make today's brittle networks easier to manage, we focus on new network designs that are inherently easier to manage and scale to many hosts, switches, and applications. We design and develop systems that scale routing, access control, and performance diagnosis, through a combination of new data structures and algorithms that make effective use of limited memory in switches and end-host based monitoring to reduce the overhead at switches. Our systems can be easily implemented with small modifications in today's switches and end hosts, as demonstrated by our prototypes built using the OpenFlow switches and Microsoft Windows servers, and our evaluation using data from AT&T networks and a deployment in a production data center.
Biography: Minlan Yu is a 5th year Ph.D. student in Princeton University. She received her B.A. in computer science and mathematics from Peking University in 2006 and her M.A. in computer science from Princeton University in 2008.
She has actively collaborated with companies such as AT&T, Microsoft, and Bell Labs. Her research interest is in solving real-world networking and distributed systems problems using efficient algorithms and data structures. Her thesis research focuses on enterprise and data center networks, by leveraging emerging techniques such as network virtualization and software-defined networking.
Host: Prof. Ramesh Govindan
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Apr 07, 2011 @ 03:30 PM - 01:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Satyen Kale, Yahoo! Research
Talk Title: Efficient Online Decision-Making and Applications to Semidefinite Programming
Abstract: Decision-making in the face of uncertainty over future outcomes is a fundamental algorithmic task, with roots in statistics and information theory, and applications in machine learning, signal processing, network routing and finance. The framework of regret minimization captures the notion of competitive online decision-making algorithms. Such algorithms are very effective for optimizing in settings where the environment is changing or just too large-scale for traditional optimization methods.
Semidefinite programming (SDP) is a widely used convex optimization technique today in operations research and computer science. The running time of SDP solvers can be quite high however. In this talk I will describe a new algorithm for online decision-making over the space of positive-semidefinite matrices. This algorithm, dubbed Matrix Multiplicative Weights, yields a general, combinatorial, primal-dual method for designing efficient algorithms for SDP. This method yields algorithms with the best known running time bounds for several graph partitioning and constraint satisfaction problems. The Matrix Multiplicative Weights algorithm also has numerous other applications in machine learning, derandomization and quantum computing which I will mention briefly.
This is joint work with Sanjeev Arora.
Biography: Satyen Kale is a postdoctoral scientist at Yahoo! Research working on algorithms for fundamental problems in Machine Learning and Optimization. His main research interests are decision making under uncertainty, statistical learning theory, combinatorial optimization, convex optimization, and more recently, algorithmic game theory. Previously, he was a postdoc at Microsoft Research New England, Cambridge, MA. In 2007, he completed his Ph.D. in the department of Computer Science at Princeton University, under the supervision of Prof. Sanjeev Arora. He completed his B.Tech in Computer Science at the Indian Institute of Technology, Bombay in 2002.
Host: Prof. Yan Liu
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Apr 12, 2011 @ 03:30 PM - 01:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Ethan Katz-Bassett, University of Washington
Talk Title: Improving Internet Performance and Availability with Reverse Traceroute
Abstract: The Internet is now central to many aspects of modern society, yet it remains remarkably fragile. Partial outages are common, and performance problems are widespread. Operators would like to address these issues, but poor diagnostic tools hamstring their efforts.
I will argue that a more robust Internet - one with the predictable performance and high availability needed to provide critical services -requires the development of a new generation of better tools. We must move towards a self-healing Internet that fixes problems in seconds, not the hours or days that operators often currently take. In my research, I have developed practical distributed systems to understand Internet problems and to provide crucial steps towards automated remediation. My systems are deployable today, without requiring modifications to the network. In the first half of the talk, I will present Reverse Traceroute, my system to measure the routing and performance behavior of reverse paths back to the local host from other networks. While tools have long existed to measure the forward direction, the reverse path has been largely opaque, hindering troubleshooting efforts. I will show how Google and other content providers can use reverse traceroute to troubleshoot their clients' performance problems. In the second half of the talk, I will focus on using Reverse Traceroute and related systems to diagnose and automatically repair availability problems, even without the participation of the network containing the failure.
Biography: Ethan Katz-Bassett is completing his Ph.D. at the University of Washington, where he previously earned his M.S. in Computer Science and Engineering. Before graduate school, he worked at the Laboratory for Advanced Software Engineering Research at the University of Massachusetts. Ethan's current research focuses on distributed systems and the Internet. He has co-authored best papers at NSDI 2008 and NSDI 2010.
Host: Prof. Ramesh Govindan
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Apr 14, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Shawn Newsam, UC Merced
Talk Title: Proximate Sensing: Inferring What-Is-Where From Georeferenced Photo Collections
Abstract: In this talk, I will describe an interesting new research direction which I term Proximate Sensing that leverages ground-level georeferenced images to map what-is-where on the surface of the Earth much like the field of Remote Sensing has done for decades using overhead imagery. Enabled by the growing collections of community contributed photo collections, Proximate Sensing represents a rich framework in which to apply and evaluate current image understanding tasks such as scene classification and object recognition as well as motivate the development of novel problems. I will describe how Proximate Sensing can be considered part of the larger phenomena of Volunteered Geographic Information (VGI), a term coined by geographer Michael Goodchild in 2007 to refer to the growing collections of geographically relevant information provided voluntarily by individuals.
While most of my talk will focus on Proximate Sensing, I will also give an overview of UC Merced, the tenth and newest campus of the University of California system, as well as briefly describe some of the other research projects my group is working on.
Biography: Dr. Shawn Newsam is an assistant professor and founding faculty of Electrical Engineering & Computer Science (EECS) at the University of California at Merced. He received a BS in EECS from UC Berkeley, an MS in Electrical & Computer Engineering (ECE) from UC Davis, and a PhD in ECE from UC Santa Barbara. Prior to joining UC Merced in 2005, he was a postdoctoral researcher in the Center for Applied Scientific Computing at the Lawrence Livermore National Laboratory (so, if you are counting, he is now at his fifth UC institution). His research interests are in image processing, computer vision, and pattern recognition particularly as applied to interdisciplinary scientific problems. He is the recipient of an Early Career Scientist and Engineer Award from the Department of Energy, and a Presidential Early Career Award for Scientists and Engineers (PECASE) from the White House Office of Science and Technology Policy.
Host: Prof. Farnoush Banaei-Kashani, USC
Location: Von Kleinsmid Center For International & Public Affairs (VKC) - 151
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Apr 14, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Romit Roy Choudhury, Duke University
Talk Title: Back to the Drawing Board: Rethinking Wireless Networks with Software Radios
Abstract: Wireless networks are mostly architected on the principles of modularity and layering. Emerging software radio platforms are beginning to blur the layer-boundaries, exporting PHY layer information to the MAC. The access to such information is proving to be invaluable, empowering researchers to question long-standing assumptions, conceive disruptive ideas, and test their feasibility on actual systems.
We have been performing such exercises at Duke and the results have been promising. For instance, while traditional MAC protocols perform contention resolution in the time domain (also called backoff), we find that OFDM based systems can migrate this process into the frequency domain, thereby eliminating a long-standing source of inefficiency. In another example, we show that collision detection (implmented in wired Ethernets) may be feasible even in wireless networks, through well-understood ideas in interference cancellation. This talk will elaborate on a number of such ongoing projects in our lab, with an emphasis on the bold and disruptive nature in these approaches. We will close not only with challenges we are struggling with, but will also look into what may lie ahead under the broader umbrella of PHY layer enabled systems.
Biography: Romit Roy Choudhury is an Assistant Professor of ECE and CS at Duke University (he recently spent the summer of 2010 as a visiting researcher at Microsoft Research, Redmond). He joined Duke in Fall 2006, after completing his PhD from UIUC. His research interests are in wireless networking mainly at the MAC/PHY layer, and in mobile computing at the application layer. He received the NSF CAREER Award in January 2008, and was appointed the Nortel Networks Assistant Professor in 2009. Visit Romit's Systems Networking Research Group (SyNRG), at http://synrg.ee.duke.edu
Host: Prof. Ramesh Govindan
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Apr 21, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Subhash Suri, UCSB
Talk Title: Paths, Trees and Polygons
Abstract: The growing scope of combinatorial algorithms often forces us to compute structures when the data are incomplete, uncertain, or time-varying. In this talk, we revisit three classical problems (Shortest Paths, Minimum Spanning Trees, and Polygon Guarding) under such informational and sensing models, and derive new complexity bounds or impossibility results.
In particular, we show that
(1) if the travel times for the edges of a graph are a (polynomial) functions of time, there can be super-polynomial number of shortest paths between two nodes,
(2) if each of the $n$ points in the plane is present only probabilistically, computing the expected length of their minimum spanning tree is intractable, and
(3) many basic geometric problems such as the Art Gallery coverage of a polygon can be solved in a "binary combinatorial sensing model" that does not require knowledge of coordinates.
Biography: Subhash Suri received his Ph.D. in Computer Science from Johns Hopkins University in 1987 and B.S. in Electronics Engineering from University Of Roorkee, India in 1981. His research interests are in Algorithms, Wireless Sensor Networks, Data Streams, Computational Geometry, and Game Theory. For more information, see http://www.cs.ucsb.edu/~suri/
Host: Prof. Gaurav Sukhatme
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Apr 26, 2011 @ 12:00 PM - 01:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Luc Vincent, Director of Engineering, Google Inc.
Talk Title: Google Street View: Image Acquisition and Computer Vision at Global Scale
Abstract: Unveiled in May 2007, the Street View feature of Google Maps is the result of a substantial engineering effort by a team including software engineers, mechanical engineers, UI designers, computer vision scientists, operations experts, and scores of others. The initial vision for Street View was provided by Google co-founder Larry Page, who personally collected street scene videos from his moving car in order to bootstrap research in this area. Turning this initial vision into a product required developing major new pieces of technology, including robust data collection platforms (vans, cars, tricycles, snowmobiles, etc.), systems for computing accurate pose from imperfect sensors, various software components to stitch, blend, color correct and warp collected imagery, efficient systems to manage a Gargantuan flow of data, a number of systems to address privacy issues, AJAX software components to integrate Street View to Google Maps, and many others. This presentation will go over some of these components and give the audience a peek at the Street View project from behind the scene.
Host: Dr. Cyrus Shahabi, USC
Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Wed, Apr 27, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Yevgeniy Dodis, NYU
Talk Title: Leftover Hash Lemma, Revisited
Abstract: The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks:
(1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v = 2*log(1/e).
(2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source.
Quite surprisingly, we show that both limitations of the LHL --- large entropy loss and large seed --- can often be overcome (or, at least,
mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for a wide range of cryptographic applications, including *all* "unpredictability" applications (signatures, MACs, etc.) and also some prominent "indistinguishability" applications, including chosen plaintext (or ciphertext) attack secure (public- or symmetric-key) encryption schemes. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}).(Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!)
Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S', and then use the resulting S' as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*.
Implication (2) suggests that the sample-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security!
The paper can be found at http://eprint.iacr.org/2011/088
Biography: Yevgeniy Dodis is an Associate Professor of computer science at New York University, which he joined in 2001 after receiving his PhD at MIT in 2000 and being a post-doc at IBM T.J.Watson Research center.
He also spent 2007-2008 academic year visiting the CRCS center at Harvard University.
Dr. Dodis' research is primarily in cryptography and network security.
In particular, he worked in a variety of areas including leakage-resilient cryptography, cryptography under weak randomness, cryptography with biometrics and other noisy data, hash function and block cipher design, protocol composition and information-theoretic cryptography. Dr. Dodis has more than 90 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including FOCS, STOC, CRYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues. Dr. Dodis is the recipient of National Science Foundation CAREER Award, IBM Faculty Award, Google Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition in 1995.
Host: Prof. David Kempe
Location: Grace Ford Salvatori Hall Of Letters, Arts & Sciences (GFS) - 118
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
Distinguished Lecture
Thu, Apr 28, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Stuart Russell, University of California, Berkeley
Talk Title: Open universes and nuclear weapons
Abstract: I will discuss a formal unification of probability theory and full (open-universe) first-order logic that allows for uncertain reasoning about unknown objects and events within a general-purpose formal language. Applications range from citation information extraction to monitoring ompliance with the Comprehensive Nuclear-Test-Ban Treaty. The second half of the talk will describe the latter application in detail.
Biography: Stuart Russell was born in Portsmouth, England in 1962. He received his B.A. with first-class honours in physics from Oxford University in 1982, and his Ph.D. in computer science from Stanford in 1986. He then joined the faculty of the University of California at Berkeley, where he is Professor (and formerly Chair) of Electrical Engineering and Computer Sciences and holder of the Smith-Zadeh Chair in Engineering. He is also an Adjunct Professor of Neurological Surgery at UC San Francisco. In 1990, he received the Presidential Young Investigator Award of the National Science Foundation, and in 1995 he was cowinner of the Computers and Thought Award. He was a 1996 Miller Professor of the University of California and was appointed to a Chancellor's Professorship in 2000. In 1998, he gave the Forsythe Memorial Lectures at Stanford University and in 2005 he received the ACM Karlstrom Outstanding Educator Award. He is a Fellow and former Executive Council member of the American Association for Artificial Intelligence and a Fellow of the Association for Computing Machinery.
He has published over 150 papers on a wide range of topics in artificial intelligence including machine learning, probabilistic reasoning, knowledge representation, planning, real-time decision making, multitarget tracking, computer vision, computational physiology, and global seismic monitoring. His books include "The Use of Knowledge in Analogy and Induction" (Pitman, 1989), "Do the Right Thing: Studies in Limited Rationality" (with Eric Wefald, MIT Press, 1991), and "Artificial Intelligence: A Modern Approach" (with Peter Norvig, Prentice Hall, 1995, 2003, 2010).
Host: Prof. Fei Sha, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
