Research Summary

Some of the things I've worked on, organized by area.

Quantum Computation:

My work in quantum computation has focused on the search for new quantum algorithms. Given the enormous effort required to implement a quantum computer and the likelihood that the achievable 'operations' per second will be much less than that of a classical computer, the only practical computational problems that will benefit will be ones where a quantum computer has a huge advantage over any classical computer.

Despite recent attempts to create a new paradigm for designing quantum algorithms using quantum random walks and the adiabatic algorithm, almost all quantum algorithms that give an exponential speedup over the best known classical algorithms have used the Fourier transform to search for symmetries.

To devise new quantum algorithms, I have taken two approaches:

Coding Theory:

Recently coding theory has been applied to the transmission of large files over the Internet to avoid having to send acknowledgements back to the sender. TCP relies on acknowledgements and subsequent retransmission to guarantee reliability. The need for feedback is a bottleneck when the latency is high, or in a multicast scenario when all of the leaves of the multicast tree are sending feedback to the root.

Erasure codes or forward error correction eliminate the need for feedback by allowing reconstruction of the original file as long as enough packets have been received. LT codes were the first class of rateless erasure codes to be discovered, the rateless property allowing the codes to adapt to the loss rate of the channel. In work with Chris Harrelson and Wei Wang, I showed analytically that LT codes work even when we use much less randomness than in the original construction.

Limited Randomness LT Codes, 41st Annual Allerton Conference on Communication, Control, and Computing, 2003.
Abstract, ps (336kB), ps.gz (156kB) or pdf (224kB).
with Chris Harrelson and Wei Wang.
The original LT codes construction assumes complete randomness. Implementations use much less randomness. We show analytically that even with this reduced randomness, LT codes are still asymptotically optimal.

Information Theory:

The capacity region of the interference channel has been an outstanding open problem in information theory for over 30 years. I obtained some asymptotic results about the maximum sumrate and the extreme points for the Han-Kobayashi achievable region (the best known achievable region) in the high SNR regime. I found some evidence suggesting that the achievable region has a simpler structure for the z-channel, when one of the receivers is not subject to interference from the other sender.

The Gaussian Interference Channel, 2000. (Unpublished)
Asymptotics (high SNR) of the Han-Kobayashi achievable region for the Gaussian interference channel.

Computational Biology:

How do we assess the quality of software for producing sequence alignments? One way is to have a test set of "gold standard" alignments that have been produced by hand. In work with Steve Chien, I examined the well known BAliBASE standard alignments and showed that the correctness of the BAliBASE alignments is questionable (version 1 and 2 give different alignments for the same set of sequences), and that scoring schemes to determine the optimality of alignments were flawed (sums-of-pairs and minimum entropy often gave better scores to the computer generated alignments than the BAliBASE alignments).

Gold Standard Alignments - 24 Carat? 2002.
Slides in pdf (128kB).
with Steve Chien.
Project report from computational biology class. Looks at the quality of the BAliBASE standard alignments.

Random Matrices/Combinatorics:

Catalan numbers arise in a natural way in random matrix theory when calculating the moments of the distribution of eigenvalues of random matrices, the most well known example being the original proof for Wigner's semi-circle law. I give a bijective proof of a combinatorial identity that appears in a similar calculation of moments.

Catalan Numbers and Random Matrices, 1999. (Unpublished)
ps (129kB) or ps.gz (33kB).
Elegant bijective proof of a combinatorial identity by counting certain Dyck paths in two different ways.

Last modified March 2, 2004