EECS 500 Homepage -- Winter 2004
Special Lectures in
COMMUNICATIONS AND NETWORKS

Lecture schedule as of 12/19/03

• Tuesday, January 6
  FIRST CLASS MEETING
  Intro to EECS 500
  
  

  ---

• Thursday, January 15
  
  Quantum Codes: Constructions and Parameters
  Dr. Alexei Ashikmin
  Mathematics of Communications Research Department
  Bell-Labs, Lucent Technologies
  
  Abstract -- It is well known that a number of computational problems can be solved on quantum computer exponentially faster than on a classical computer. One of the main problems in building aquantum computer is its unavoidable coupling with an environment. This coupling results in decoherence of a quantum state. The only way of fighting the decoherence is quantum error correction.
  
  In my talk I will give a general introduction to quantum error correcting codes. In particular, I will give a definition of a quantum code, its minimum distance and its distance distribution. After that I will survey the state of our knowledge about quantum codes, present results on an explicit construction of asymptotically good quantum codes, upper and lower bounds for the minimum distance of a quantum code, and the probability of the undetected error.

  ---

• Thursday, January 22
  
  Network Coding: From Graph Theory to Algebraic Geometry
  Dr. Emina Soljanin
  Bell-Labs, Lucent Technologies
  
  Abstract -- The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. Our idea was to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory and algebraic geometry. This talk will describe our approach to the network coding problem and its strengths in deriving theoretical results and practical codes.

  ---

• Tuesday, January 27
  
  Simple, Scaleable Network Algorithms
  Prof. Balaji Prabhakar
  Stanford University
  
  Abstract -- Randomized algorithms are particularly well-suited for coping with the so-called "curse of dimensionality" from which many networking problems suffer. The main idea of randomized algoriths is simple to state: Rather than contend with a large state space, the trick is to base decisions upon a few randomly chosen samples.
  
  This talk will illustrate the use of randomization in devising simple-to-impelement, high-performance network algorithms; specifically, for switch scheduling, web caching, and bandwidth partitioning.

  ---

• Thursday, February 5
  
  From Wireless and Sensor Networks to Convergence: Theory, Protocols, and Architecture
  Prof. P. R. Kumar
  Coordinated Science Laboratory
  University of Illinois at Urbana-Champaign
  
  Abstract -- We begin with the question: How much traffic can wireless networks carry, and how should information be transported across them? We present a network information theory to address this question.
  
  Then we turn to the protocol needs of ad hoc wireless networks. We present three such protocols for problems arising especially in wireless networks - power control (COMPOW), media access (SEEDEX), and routing (STARA). We highlight not only the algorithms, but also the role of architecture in software implementation of protocols.
  
  Next we turn to the emerging area of sensor networks, and address the issue of data fusion. We present some results on how computation and communication should be organized over the network in order to determine functions of the sensor measurements at a fusion center.
  
  Finally, we address the issue of where we are headed in the next phase of the information technology revolution. We begin with the historical context, and then to the possible oncoming convergence of control with communication and computation. We highlight the importance of architecture and abstractions. We present some middleware efforts underway at the Information Technology lab at the University of Illinois.
  
  (Joint work with G. Baliga, A. Giridhar, S. Graham, K. Huang, V. Kawadia, S. Narayanaswamy, R. Rozovsky, P. Gupta, V. Borkar).
  
  

  ---

• Thursday, February 12
  
  What Use is the Zeta Function?
  Dr. John Derbyshire
  
  
  Abstract -- John Derbyshire, author of the book PRIME OBSESSION, will speak about his experiences in attempting to bring an understanding of the Riemann Hypothesis to a general audience. What is the Hypothesis, and what accounts for its current prominence in lists of great unsolved problems? Does it have any practical relevance? If the Hypothesis were to be resolved tomorrow, what would be the consequences? Why did the author (who is a journalist, not a professional mathematician) feel moved to write a popular book about it? Mr. Derbyshire will go on to develop some general ideas about the place of math in the consciousness of well-educated but non-mathematical Americans, based on reactions to his book in particular, and to the current fashion for pop-math books in general. He will report on the kinds of questions that non-mathematical readers typically ask him, especially the question: What USE is it? Throughout his talk Mr. Derbyshire will draw on examples from the history of mathematics. He will offer ideas about the development of mathematical thinking, the place of math in the popular consciousness, and the future of math.

  ---

• Tuesday, March 2
  
  Extrinsic Information Transfer Charts as a Design Tool for Iterative Processors
  Dr. Gerhard Kramer
  Lucent Technologies
  
  Abstract -- Iterative processors have become an important building block of communications receivers. This talk gives an introduction to a design tool that has proven rather accurate in predicting the behavior of such devices. The tool, called the extrinsic information transfer (EXIT) chart, was developed by taking an engineering "transfer function" approach to analysis. We illustrate the use of an EXIT chart for turbo codes, and show how it guides the choice and design of codes for other problems such as modulation, detection, equalization, and so forth. Design examples for multi-antenna communication are presented. We further outline theoretical progress on understanding why the tool works so well, and how one might improve its predictions.

  ---

• Thursday, March 18
  
  H Stands for Hydrogen . . . and Humility
  Dr. John Rigden
  American Institute of Physics
  
  Abstract -- Simplicity need not be trivial. Simplicity can be profound. The hydrogen atom is Nature's simplest atom: a single proton surrounded by a solitary electron. This simplicity, however, belies the importance of hydrogen for 20th century science and technology. It is hydrogen that provides the most striking example of how experimental data and physical theory work together to advance our understanding of physical phenomena. Repeatedly the hydrogen atom has surprised physicists and, in the process, has brought basic new insights into the workings of Nature. Hydrogen has also humbled physicists as it has defied their most confident predictions. Through the simple hydrogen atom the door was opened to nuclear magnetic resonance (NMR) and the powerful diagnostic medical tool MRI; through hydrogen the door was opened to atomic clocks. The role of hydrogen has been prominent in working out details of atomic structure and has made seminal contributions to the understanding of nuclear structure. The hydrogen atom has enabled us to map the Milky Way and probe galactic structure. The hydrogen atom has provided an empirical check on Big Bang cosmology. And yet, the hydrogen atom still beckons, still calls for our attention. Whenever scientists are tempted to think they have a hammer-lock on Nature, it would be good to remember that H stands for hydrogen and humility.

  ---

• Thursday, March 25
  
  PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks
  Prof. Pravin Varaiya
  Dept. of Electrical Engineering and Computer Science
  University of California, Berkeley
  
  Abstract -- We consider a class of sensor networks with two special characteristics. First, the nodes periodically generate data for transfer to a distinguished node called the access point. Second, the nodes are (transmit) power and energy limited, but the access point, which communicates with the 'outside world', is not so limited. Such networks might be used for instance when traffic on a freeway or at an urban street intersection is periodically sensed for purposes of control. We propose a medium access control scheme, called PEDAMACS, for this special class of networks.
  
  PEDAMACS uses the high-powered access point to synchronize the nodes and to schedule their transmissions and receptions. The protocol first enables the access point to gather topology (connectivity) information. A polynomial-time scheduling algorithm then determines when each node should transmit its data, and the access point announces the transmission schedule to the other nodes.
  
  Because PEDAMACS schedules node transmissions, its performance is much better than that of protocols designed for more general contention (or random access) networks in terms of power consumption, delay, fairness, and congestion control. The comparison is based on simulations in TOSSIM, a simulation environment for TinyOS, the operating system for the Berkeley sensor nodes. For our traffic application, the power consumption of a PEDAMACS network is 100 times lower than a contention network, making sensor network technology economically viable.
  
  
  

  ---

• Tuesday, March 30
  
  COMPARING STRENGTH OF LOCALITY OF REFERENCE -- Popularity, majorization, and some folk theorems for the miss rate and output of caches
  
  Prof. Armand Makowski
  Dept. of Electrical and Computer Engineering
  University of Maryland at College Park
  
  Abstract -- The performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. Yet, like the notion of burstiness used in traffic modeling, locality of reference, while endowed with a clear intuitive content, admits no simple definition. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference.
  
  We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. More specifically, we focus on two "folk theorems," namely (i) The stronger the locality of reference, the smaller the miss rate of the cache; (ii) Good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream.
  
  We discuss results concerning these two folk theorems in the context of a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). As we propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, we introduce the notion of majorization as a means of capturing this degree of skewness.
  
  We show that these folk theorems hold for caches operating under a large class of cache replacement policies, including the optimal policy A_0 and the random policy, but may fail under the LRU and CLIMB policies. In addition, we explore how the majorization of popularity distributions translates into comparisons of three well-known locality of reference metrics, namely the inter-reference time, the working set size and the stack distance.
  
  

  ---

• Thursday, April 8
  
  Some Analysis and Applications of Imate Registration
  
  Prof. Peter Ramadge
  Princeton University
  
  Abstract -- When a sequence of images are taken by a camera that is moving or when the scene contains objects that are moving, the images often need to be aligned or registered with each other for purposes of further processing. Indeed image registration is often a required precursor to many other sophisticated image and video processing operations.
  
  I will present some recent results on this problem in two application domains. First, I give results on the growth of the error in registering a sequence of images. Attention is restricted to the simple and somewhat restrictive class of 2-D translations. However, the main objective is not to study the registration problem itself but rather the growth rate of the registration error as the number of images in the sequence increases. Restricting attention to the simple class of 2-D translations allows us to make analytical headway on this problem. The problem is posed as an estimation problem on a graph. A real valued function on the nodes of the graph is to estimated from noisy differential measurements of the function values. Two cases of particular interest are the linear graph and a circular graph with N nodes. The main result is that increasing the size of the local group of nodes over which measurement is performed has a significant effect on the accumulation of the registration error. We show this through approximation, upper bounds on error growth, and in some special cases by closed form expressions for the worst case error variance.
  
  A second motivating application is the registration of images from different modalities, e.g. MRI with PET images. Time permitting, I will discuss some observations on registration metrics and computational issues and presented a new algorithm that is grounded in the Euclidean minimal spanning tree estimation of entropy.

  ---

  Sponsors:

  Lucent Technologies and the University of Michigan Dept. of Electrical and Computer Engineering and College of Engineering.