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