UC San Diego Information Theorists Show Up in Force at IEEE International Symposium
San Diego, July 9, 2010 -- More than a dozen research papers at the 2010 IEEE International Symposium on Information Theory (ISIT) were co-authored by researchers from the University of California, San Diego, and the papers presented by graduate students resonated with reviewers. Among 250 student papers at the June conference in Austin, Texas, 44 were selected as finalists by the Information Theory Society Award Committee, and five of those were co-authored by students affiliated with the Information Theory and Applications Center (ITA), based at the UCSD division of the California Institute for Telecommunications and Information Technology (Calit2). The papers were evaluated based on technical content and the quality of the presentation at ISIT, and now the Society has announced that one of the UCSD finalists is also a Best Student Paper Award winner for 2010.
|
Acharya’s prize-winning paper – “On Reconstructing a Sequence from its Subsequence Compositions” – was co-authored with Hirakendu Das, Olgica Milenkovic, Shengjun Pan and ITA director Alon Orlitsky. The paper considered the simple problem of reconstructing a string from the compositions of all its substrings. The problem is motivated by mass-spectrometry protein sequencing, where the protein molecule is broken up into segments whose weights and hence amino-acid composition can be determined. The segment compositions are then used to infer the protein's sequence of amino acids, and hence its functionality. Viewing strings as bivariate polynomials, Jayadev and his co-authors converted the reconstruction problem into that of polynomial factorization. They then used this formulation to show that strings of length one short of a prime can be uniquely reconstructed, while for other lengths, reconstruction may not be unique.
|
The other UCSD finalists' papers were:
- “Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes,” co-authored by Hessam Mahdavifar and ECE professor Alexander Vardy. Back in 1975, Aaron Wyner characterized the maximum rate (in bits per second, say) at which one person can communicate with another while satisfying both the reliability and the security requirements. Reliability means that the intended recipient’s probability of error in recovering the entire message should be very small, while security means that a potential eavesdropper should not be able to get much information about the message (even using a quantum computer or non-deterministic Turing machine). This rate is called the secrecy capacity, and the problem of actually constructing reliable and secure coding schemes that achieve secrecy capacity remained open for 35 years. In their paper, however, Mahdavifar and Vardy constructed just such a scheme. Their encoding and decoding algorithms are based upon polar codes, which are widely regarded as the most exciting recent breakthrough in coding theory. They showed how polar codes can be used to guarantee not only reliability but also security against eavesdroppers. In fact, their coding scheme provides much stronger security guarantees than those envisioned by Wyner in 1975. To read the paper, go to http://arxiv.org/abs/1001.0210.
- “Function computation via subspace coding,” by Nikhil Karamchandani, in collaboration with a student at Switzerland’s EPFL, Lorenzo Keller, and their respective advisors, ECE professor Massimo Franceschetti and EPFL professor Christina Fragouli. One node in a network may wish to compute a function of the values stored by some other nodes, e.g., learning if the temperature in a building is so high as to trigger an alarm, while a collection of sensors scattered inside the building are measuring it. A simple solution is to convey the different temperature values from the sensor nodes to the final destination via multi-hop relay and finally perform the computation there. A more elaborate and more efficient solution may be to combine values at the intermediate nodes by encoding them, so that the function value is computed ‘along the way’ while it reaches the destination node. This is called network coding and it has received enormous attention in the literature in the past 10 years. The network coding approach, however, requires the intermediate nodes to have knowledge of the function to be computed, and to adjust their encoding operations so that this can be correctly evaluated. Karamchandani and his colleagues came up with the idea of applying a special coding technique called vector-subspace coding (credited to Ralf Koetter and Karl Kschischang). This allows the relay nodes to perform the same operation on the incoming code words, irrespective of the target function to be computed. The function is only known to the sources, who select their codebooks according to it, and inject into the network the basis vectors of the corresponding subspaces, which are then randomly combined at the intermediate nodes before reaching the destination. Nikhil and his co-authors designed a number of near-optimal coding schemes of this type for a variety of functions, as well a general coding scheme for arbitrary functions. The paper can be downloaded at http://infoscience.epfl.ch/record/143339/files/CompSubspaces.pdf.
- “Multiple Error-Correcting WOM-Codes,” by Eitan Yaakobi, with co-authors and ECE professors Paul Siegel, Alexander Vardy and Jack Wolf. A write-once memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the “zero” state to the “one” state only once. Examples of WOMs include punch cards and write-once optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the “one” state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. A WOM-code that uses n cells to store k bits t times is called an [n, k, t] WOM-code. The WOM model is also relevant to flash memories, which have become ubiquitous in recent years. In a flash memory, cells are arranged in rectangular arrays called “blocks.” Starting from an “all-zero” state, information is recorded in the blocks on a row-by-row basis. However, in order to rewrite a row in a previously written block, the entire block must first be erased, returning it to the “all-zero” state. This block-erase operation introduces a significant delay and also has a detrimental effect on the lifetime of the memory. WOM-codes offer a way to reduce the number of such block erasures. Eitan Yaakobi and his coauthors addressed the problem of designing efficient WOM-codes that can also handle errors. They first showed how to transform any existing [n, k, t] WOM-code into an [n+t, k, t] WOM-code that can detect a single error in any cell in each of t writes. They then described a code design technique that combines a WOM-code, a single-error-detecting WOM-code, and a conventional single-error-correcting code to produce a single-error-correcting WOM-code. Extending this approach, they presented a code design methodology that yields WOM-codes capable of handling any specified number of errors. The construction is based upon a special class of multiple-error-correcting codes that they call “strong” codes. Examples of strong error-correcting codes capable of handling two errors or three errors were identified and used in the construction of practical double-error-correcting and triple-error-correcting WOM-codes.
- “Linear Sum Capacity for Gaussian Multiple Access Channel with Feedback,” by Ehsan Ardestanizadeh, with Michele Wigger of Telecom ParisTech and ECE professors Young-Han Kim and Tara Javidi. Feedback plays many interesting roles in communication over networks. One such role is to build cooperation among different nodes to increase data rates and improve reliability of communication, which is manifest in multiple access (or cellular uplink) systems. As a canonical model to study the role of feedback in multiple access systems, the additive white Gaussian noise (AWGN) multiple access channel (MAC) with feedback is often studied, where the input signal of each sender is corrupted by interference from other senders and ambient noise, and each sender can sequentially adjust its signal based on the feedback from the receiver. Despite significant contributions by Cover, Leung, Ozarow, Thomas, Pombra, Ordentlich, Kramer, and Gastpar, however, finding the optimal coding strategy for the AWGN-MAC is not known in general. Now, using myriad techniques from probability, control, estimation, optimization and information theory, Ehsan Ardestanizadeh and coauthors showed that a simple coding strategy of ‘iterative refinement’ can be optimal among all linear feedback codes, where each sender iteratively refines the receiver's knowledge about its message. This iterative refinement strategy is coordinated among many senders to maximize coherent transmission. Download the paper at http://arxiv.org/abs/1002.1781.
Next fall ITA will host a colloquium where the five UCSD finalists will present their papers. Also, many of the researchers who participated at the Austin symposium will be in San Diego next February 6-11, when ITA hosts its sixth annual Information Theory and Applications Workshop.
Media Contacts
Doug Ramsey, 858-822-5825, dramsey@ucsd.edu
Related Links
ISIT 2010
ISIT Student Paper Awards
Information Theory and Applications Center
ITA Workshop 2011
UCSD Electrical and Computer Engineering
Jacobs School of Engineering
Calit2