Lawrence Ip > Papers |

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

**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).

**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.

**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.

**The Gaussian Interference Channel**, 2000. (Unpublished)

Asymptotics (high SNR) of the Han-Kobayashi achievable region for the Gaussian
interference channel.

**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