Papers

Some of the things I've worked on, in approximate reverse chronological order. My research summary places all this work in context.

Quantum Computation:

Shor's Algorithm is Optimal, 2003. (Submitted)
Abstract, ps (350kB), ps.gz (161kB) or pdf (196kB).
The standard algorithm for the abelian hidden subgroup problem implements the optimal measurements. For some nonabelian groups we find the optimal measurements by solving a semidefinite program and show that the standard algorithm is no longer optimal.

Quantum Algorithms for some Hidden Shift Problems, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003.
Abstract, ps (537kB), ps.gz (256kB) or pdf (199kB). Also quant-ph/0211140.
with Wim van Dam and Sean Hallgren.
Quantum algorithm for the shifted Legendre symbol problem and its generalizations.

Solving Shift Problems and the Hidden Coset Problem Using the Fourier Transform, 2002.
Abstract, ps (151kB), ps.gz (57kB), pdf (170kB) or djvu (81kB). Also quant-ph/0205034.
Earlier version that treats the problem from a matrix factorization viewpoint (as opposed to the deconvolution viewpoint).

Coding Theory:

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.

Computational Biology:

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

Information Theory:

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

Random Matrices/Combinatorics:

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