Skip to main content

31 OCTOBER 2005
Speaker: Biswanath Mukherjee
Title: Optical Networking: Its Inter-Disciplinary Nature and New Research Challenges
Host School: NC State University
Duke Host:
UNC Host: 
Kevin Jeffay (
NCSU Hosts: Rudra Dutta ( and David Thuente

Optical fiber is the medium of choice for building high-capacity networks: from broadband access networks to regional metro networks to long-haul backbone networks. After the telecom bubble burst in 2000, the optical networking (ON) industry went into a consolidation phase. But, in 2004, ON equipment manufacturers started reporting profits again, and this $5-Billion industry is poised to double in size over the next 4-5 years.

Successful growth of ON, however, will occur only if researchers from multiple disciplines (physics, optics, communications, networking, computer algorithms, operations research, and business school) are able to work together in identifying, understanding (one another’s jargons), and effectively solving the important and exciting inter-disciplinary problems in the field. A sampling of these inter-disciplinary opportunities and new research challenges will be outlined in this talk.

Biswanath Mukherjee received the B.Tech. (Hons) degree from Indian Institute of Technology, Kharagpur (India) in 1980 and the Ph.D. degree from University of Washington, Seattle, in June 1987. At Washington, he held a GTE Teaching Fellowship and a General Electric Foundation Fellowship.

In July 1987, he joined the University of California, Davis, where he has been Professor of Computer Science since July 1995, and served as Chairman of Computer Science during September 1997 to June 2000. He is a winner of the 2004 Distinguished Graduate Mentoring Award at UC Davis. Two PhD Dissertations (by Dr. Laxman Sahasrabuddhe and Dr. Keyao Zhu), which were supervised by Professor Mukherjee, were winners of the 2000 and 2004 UC Davis College of Engineering Distinguished Dissertation Awards.

He is co-winner of paper awards presented at the 1991 and the 1994 National Computer Security Conferences. He serves or has served on the editorial boards of the IEEE/ACM Transactions on Networking, IEEE Network, ACM/Baltzer Wireless Information Networks (WINET), Journal of High-Speed Networks, Photonic Network Communications, Optical Network Magazine, and Optical Switching and Networking journal. He also served as Editor-at-Large for optical networking and communications for the IEEE Communications Society. He served as the Technical Program Chair of the IEEE INFOCOM ’96 conference. He also serves as Chairman of the IEEE Communication Society’s Optical Networking Technical Committee (ONTC). He is Editor of Springer’s Optical Networks Book Series.

Mukherjee is author of the textbooks “Optical WDM Networks” (to be published by Springer in 2005) and “Optical Communication Networks” (published by McGraw-Hill in 1997). He is a Member of the Board of Directors of IPLocks, Inc., Silicon Valley startup company founded in March 2002. He has consulted for and served on the Technical Advisory Board (TAB) of a number of startup companies in optical networking. His current TAB appointments include: Teknovus, Intelligent Fiber Optic Systems, and LookAhead Decisions Inc.


14 NOVEMBER 2005
Speaker: David Johnson
Title: Compressing Rectilinear Pictures, with Applications to Internet Routing
Host School: NC State University
Duke Host: 
UNC Host: 
Jasleen Kaur (
NCSU Host: Matt Stallman (
Change to UNC venue: This talk will be viewed in Peabody 08 at 4 p.m.

We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers. This model is a generalization of one previously studied in the context of rectilinear picture compression. It embodies an optimization problem that arises when drawing figures using common software packages such as Excel and Xfig.

Here the goal is to create a colored rectilinear pattern within an initially white square canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Motivated by the ACL application, we study the special case in which all rectangles must be strips that extend either the full length or the full height of the canvas. We provide several equivalent characterizations of the patterns achievable in this special case and present a polynomial-time algorithm for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also bound the improvement one can obtain by using arbitrary rectangles in the construction of such patterns, and analyze heuristics for the case of general patterns.

This is joint work with David Applegate, Gruia Calinescu, Howard Karloff, Katrina Ligett, and Jia Wang.

David S. Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his Ph.D from MIT. The author of over 100 technical papers, he is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize of the Operations Research Society of America (1979). His research interests (in addition to the theory of NP-completeness) include approximation algorithms for combinatorial problems, and the experimental analysis of algorithms, with special emphasis on bin packing, graph coloring, and the traveling salesman problem. As one of the founders of ACM’s Kanellakis Prize, he is particularly interested in recognizing and encouraging the interaction between theory and practice in computer science.


23 JANUARY 2006
Speaker: John A. Stankovic, Computer Science, University of Virginia
Title: Self-Organizing Wireless Sensor Networks in Action
Host School: NC State University
Duke Host: TBA
UNC Host: 
Sanjoy Baruah (
NCSU Host: Vincent Freeh ( and Xiaosong Ma(

Wireless sensor networks (WSN), composed of large numbers of small devices that self-organize, are being investigated for a wide variety of applications. Two key advantages of these networks over more traditional sensor networks are that they can be dynamically and quickly deployed, and that they can provide fine-grained sensing. Applications, such as emergency response to natural or manmade disasters, detection and tracking, and fine grained sensing of the environment are key examples of applications that can benefit from these types of WSNs. Current research for these systems is widespread. However, many of the proposed solutions are developed with simplifying assumptions about wireless communication and the environment, even though the realities of wireless communication and environmental sensing are well known. Many of the solutions are evaluated only by simulation. In this talk I describe a fully implemented system consisting of a suite of more than 30 synthesized protocols. The system supports a power aware surveillance and tracking application running on 203 motes and evaluated in a realistic, large-area environment. Technical details and evaluations are presented for power management, dynamic group management, and for various system implementation issues. Several illustrations of how real world environments render some previous solutions unusable will also be given.

Professor John A. Stankovic is the BP America Professor in the Computer Science Department at the University of Virginia. He recently served as Chair of the department, completing two terms (8 years). He is a Fellow of both the IEEE and the ACM. He also won the IEEE Real-Time Systems Technical Committee’s Award for Outstanding Technical Contributions and Leadership. Professor Stankovic also served on the Board of Directors of the Computer Research Association for 9 years. Before joining the University of Virginia, Professor Stankovic taught at the University of Massachusetts where he won an outstanding scholar award. He has also held visiting positions in the Computer Science Department at Carnegie-Mellon University, at INRIA in France, and at the Scuola Superiore S. Anna in Pisa, Italy. He was the Editor-in-Chief for the IEEE Transactions on Distributed and Parallel Systems and is a founder and co-editor-in-chief for the Real-Time Systems Journal. He was also General Chair for ACM SenSys 2004 and will serve as General Chair for ACM/IEEE Information Processing in Sensor Networks (IPSN) 2006. His research interests are in distributed computing, real-time systems, operating systems, and wireless sensor networks. Prof. Stankovic received his PhD from Brown University.


30 JANUARY 2006
Speaker: Steve Bellovin, Columbia University
Title: Permissive Action Links, Nuclear Weapons, and the History of Public Key Cryptography
Host School: UNC-Chapel Hill
Duke Host: Alan Biermann (
UNC Host: 
Frederick Brooks (
NCSU Host: Peng Ning (

From a security perspective, command and control of nuclear weapons presents a challenge. The security mechanisms are supposed to be so good that they’re impossible to bypass. But how do they work? Beyond that, there are reports linking these mechanisms to the early history of public key cryptography. We’ll explore the documented history of both fields, and speculate on just how permissive action links — the “combination locks” on nuclear weapons — actually work.

Steven M. Bellovin is a professor of computer science at Columbia University, where he does research on networks, security, and especially why the two don’t get along. He joined the faculty in 2005 after many years at Bell Labs and AT&T Labs Research, where he was an AT&T Fellow. He received a BA degree from Columbia University, and an MS and PhD in Computer Science from the University of North Carolina at Chapel Hill. While a graduate student, he helped create Netnews; for this, he and the other perpetrators were award the 1995 Usenix Lifetime Achievement Award. He is a member of the National Academy of Engineering and the Department of Homeland Security’s Science and Technology Advisory Board.

Bellovin is the co-author of “Firewalls and Internet Security: Repelling the Wily Hacker,” and holds several patents on cryptographic and network protocols. He has served on many National Research Council study committees, including those on information systems trustworthiness, the privacy implications of authentication technologies, and cybersecurity research needs; he was also a member of the information technology subcommittee of an NRC study group on science versus terrorism. He was a member of the Internet Architecture Board from 1996-2002; he was co-director of the Security Area of the IETF from 2002 through 2004.


13 FEBRUARY 2006
Speaker: Alan Burns, University of York, U.K.
Title: Modeling Temporal behaviour in Complex Socio-Technical Systems
Host School: UNC-Chapel Hill
Duke Host: Jun Yang (
UNC Host: 
James Anderson (
NCSU Host: Frank Mueller (


See speaker’s homepage.


10 APRIL 2006
Speaker: Nicholas Ayache, Research Director, Epidaure/Asclepios Laboratory, INRIA Title:Computational Models for Medical Image Analysis
Host School: UNC-Chapel Hill
Duke Host: Jun Yang (
UNC Hosts: 
Steve Pizer ( and Guido Gerig (
NCSU Host: Khaled Harfoush (

Medical image analysis brings about a revolution to the medicine of the 21st century, introducing a collection of powerful new tools designed to better assist the clinical diagnosis and to model, simulate, and guide more efficiently the patient’s therapy. A new discipline has emerged in computer science, closely related to others like computer vision, computer graphics, artificial intelligence and robotics.

In this talk, I describe the increasing role of computational models of anatomy and physiology to guide the interpretation of complex series of medical images, and illustrate my presentation with applications to cardiac and brain diseases. I conclude with some promising trends, including the analysis of in vivo microscopic images.

References available at

Nicholas Ayache is a Research Director at INRIA (French Research Institute in Computer Science and Automatic Control), Sophia-Antipolis, France, where he has been the scientific leader of the EPIDAURE research group on medical image analysis and robotics since 1993. He is currently teaching graduate courses in Computer Vision and Medical Imaging at Ecole Centrale Paris and Ecole Normale Supérieure (Cachan), and was previously teaching at the Universities of Paris XI and Nice-Sophia Antipolis. Since 1984, he has been a scientific consultant for several industrial companies or international research institutes, and participated in the creation of several start-up companies in image processing, computer vision, and bio-medical imaging.

Dr. Ayache received his Ph.D in 1983, and his “Thèse d’Etat” in 1988, both in computer science, from the University of Paris XI, on the development of vision cababilities for autonomous robots, more precisely on topics related to model based object recognition, passive stereovision, and multisensor fusion. Since 1988, Dr. Ayache’s research interests have been in Medical Image Analysis (including shape and motion representation, rigid and nonrigid registration, tracking and analysis of deformable objects), simulation of surgery (including the modelling of soft tissue), and image guided therapy (in particular in the context of medical robotics). Dr. Ayache has also been involved in the analysis of functional images and their application to medicine and neurosciences, and more recently in the analysis of microscopic images for medical or biological applications. Dr. Nicholas Ayache is the author and co-author of more than 200 scientific publications in these domains.

Dr. Ayache has several editorial responsabilities : he is the co-founder and co-Editor in Chief of the scientific journal Medical Image Analysis (Elsevier), an Associate Editor of Transactions on Medical Imaging (IEEE), a member of the editorial board of Computer Assisted Surgery (Wiley), Mathematical Modeling and Analysis (EDP Science), and Medical Imaging Technology (Japanese Society of Medical Imaging). He was associate editor of the Int. Journal of Computer Vision (Kluwer, 1992-2004), advisory editor of Videre-Computer Vision Research Journal (MIT-Press, 1996-2000), and associate editor of IEEE Trans. on Robotics and Automation (1988-93).

Dr. Ayache is the author of the book Artificial Vision for Mobile Robots (MIT-Press) ( “Vision stéréoscopique et perception multisensorielle”, Inter-Editions) and Editor of the book “Computational Models for the Human Body”. He chaired the first International Conference on Computer Vision, Virtual Reality, and Robotics in Medicine (CVRMed) held in Nice in April 1995, and co-chaired the First Symposium on Surgery Simulation and Soft Tissue Modeling in 2003. Dr Ayache has been serving on the editorial board of major conferences in Medical Imaging, Computer Vision, Visualisation, and Robotics including MICCAI, ISBI, CVPR, ECCV and ICCV.


17 APRIL 2006
Speaker: Anne Condon, University of British Colombia
Title: RNA Molecules: Glimpses Through an Algorithmic Lens
Host School: Duke University
Duke Host: Carla Ellis ( and John Reif (
UNC Host: 
Jan Prins (
NCSU Host:

RNA molecules are increasingly in the spotlight, in recognition of the important roles they are now knolwn to play in our cells, and their promise in therapeutics. In this talk, we will give some background on these fascinating molecules, and will describe ways in which computer algorithms can help shape our understanding of their structure – particularly secondary structure – and function.

My research interests are in computational complexity theory and biomolecular computation. In the area of computational complexity, I am generally interested in randomized models of computation and randomized algorithms.

My work in the area of biomolecular computation focuses on design of DNA strands for molecular computations, and also on surface based DNA computations, in collaboration with the Wisconsin DNA Computing Project A goal of this research, which involves chemists, materials scientists, and computer scientists at U. Wisconsin is to store digital information in surface-bound DNA molecules in a scalable fashion and to perform logical operations on that information using enzymatic and chemical processes, thereby “computing” with DNA.

I am also interested in automatic methods for showing that cache coherence protocols implement certain memory models, such as sequential consistency.


24 APRIL 2006

Speaker: Michael Kearns, University of Pennsylvania
Title: Behavioral Graph Coloring
Host School: Duke University
Duke Host: Sayan Mukherjee (
UNC Host: David Plaisted (
NCSU Host:

The pioneering work of Travers and Milgram in 1969 established the now-familiar folklore of “six degrees” of separation in natural social networks. More recently, researchers including Jon Kleinberg and Duncan Watts have explored the algorithmic aspects of how messages are forwarded in such networks. Perhaps the computer science view of this fascinating line of thought can be best summarized as follows: Using relatively local information, distributed human organizations can compute good approximations to the all-pairs shortest paths problem. What other sorts of distributed optimization problems can humans networks solve?

In this talk, I will describe the preliminary but thought-provoking findings of a series of behavioral experiments we have been performing at Penn. Human subjects attempt to perform distributed graph coloring using a system that controls network structure, information conditions, incentives, and a variety of other variables of interest. The experiments shed early light on whether such problems can be solved by human networks, under what conditions, and what algorithms they seem to adopt.

Joint work with Nick Montfort, Huanlei Ni, and Siddharth Suri.

I am a professor in the Computer and Information Science Department at the University of Pennsylvania, where I hold the National Center Chair in Resource Management and Technology.

I am also the head of quantitative strategy development in the Equity Strategies department of Lehman Brothers in New York City. (Please send any Lehman-related email to

At Penn, I am the co-director (with Linguistics professor Mark Liberman) of Penn’s interdisciplinary Institute for Research in Cognitive Science. I also have a secondary appointment in the Operations and Information Management (OPIM) department of the Wharton School.

In 2001, I took a brief sabbatical from pure research as Chief Technology Officer of Syntek Capital.

I spent the decade 1991-2001 in basic AI and machine learning research at AT&T Labs and Bell Labs. During my last four years there, I was the head of the AI department, which conducted a broad range of systems and foundational AI work. During my time at AT&T/Bell Labs, I also served as the head of the Machine Learning department, and as the head of the Secure Systems Research department.

I joined the Penn faculty in January 2002.