Publication List
Last Updated: Woefully out of date
I have divided my publications list into the following categories:
Some of these papers, and possibly some preprints not in this list,
are available electronically at my
preprint page.
Many of the quantum computing papers are available at the
Los Alamos
quantph preprint archive.

P. W. Shor, Algorithms for quantum computation: Discrete logarithms and
factoring, Proc. 35nd Annual Symposium on Foundations of Computer
Science (Shafi Goldwasser, ed.), IEEE Computer Society Press (1994),
124134.

P. W. Shor, Scheme for reducing decoherence in quantum computer memory,
Phys. Rev. A 52, pp. 24932496 (1995).

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus,
P. Shor, T. Sleator, J. Smolin, and H. Weinfurter, Elementary gates for
quantum computation, Phys. Rev. A, 52, pp. 34573467 (1995).

I. L. Chuang, R. Laflamme, P. W. Shor and W. H. Zurek, Quantum computers,
factoring and decoherence, Science, 270, pp. 16351637 (1995).

A. R. Calderbank and P. W. Shor, Good quantum errorcorrecting codes exist,
Phys. Rev. A 54, pp. 10981106 (1996).

D. P. DiVincenzo and P. W. Shor, Fault tolerant error correction
with efficient quantum codes, Phys. Rev. Lett. 77,
pp. 32603263 (1996).

P. W. Shor, Faulttolerant quantum computation, Proc. 37nd Annual Symposium
on Foundations of Computer Science, IEEE Computer Society Press, pp. 5665 (1996).

A. R. Calderbank, E. Rains, P. W. Shor and N. J. A. Sloane, Quantum error
correction and orthogonal geometry, Phys. Rev. Lett. 78,
pp. 405408 (1997).

P. W. Shor, Polynomialtime algorithms for prime factorization and
discrete logarithms on a quantum computer, SIAM J. Computing
26, pp. 14841509 (1997).

P. Shor and R. Laflamme, Quantum analog of the MacWilliams
identities in classical coding theory, Phys. Rev. Lett.
78, pp. 16001603 (1997).

E. M. Rains, R. H. Hardin, P. W. Shor and N. J. A. Sloane,
A nonadditive quantum code, Phys. Rev. Lett.
79, pp. 953954 (1997).

D. P. DiVincenzo, P. W. Shor and J. A. Smolin,
Quantumchannel capacity of very noisy channels
Phys. Rev. A. 57 pp. 830839 (1998).

A. R. Calderbank, E. Rains, P. W. Shor, and N. J. A. Sloane,
Quantum error correction via codes over GF(4),
IEEE Transactions on Information Theory, to appear.

A. Aggarwal, M. Klawe, S. Moran, P. Shor and R. Wilber, Geometric
applications of a matrix searching algorithm, Algorithmica 2,
pp. 195208 (1987). Preliminary version: Proc. 2nd ACM Annual
Symposium on Computational Geometry, pp. 285292 (1986).

A. Aggarwal, L. J. Guibas, J. Saxe and P. W. Shor, A linear time algorithm for
computing the Voronoi diagram of a convex polygon, Discrete and
Computational Geometry 4, pp. 591604 (1989). Preliminary
version: Proc. 19th Annual ACM Symposium on Theory of Computing,
pp. 3945 (1987).

K. L. Clarkson and P. W. Shor, Applications of randomization in computational
geometry II, Discrete and Computational Geometry 4,
pp. 387421 (1989). Part of this work appeared originally in:
K. L. Clarkson and P. W. Shor, Algorithms for diameter and convex hull that
are fast, incremental, and randomized, 4th ACM Symposisum on
Computational Geometry, pp. 1217 (1988).

A. Aggarwal, S. Moran, P. W. Shor and S. Suri, Computing the minimum visible
vertex distance between two polygons,
Proc. of the Workshop on Algorithms and Data Structures
(F. Dehne, J.R. Sack and N. Santono eds.),
Lecture Notes in Computer Science Vol. 382,
SpringerVerlag, pp. 115119 (1989).

P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds on the
length of general DavenportSchinzel sequences, J. Combinatorial
Theory A 52, pp. 228274 (1989).

A. Aggarwal, M. Klawe and P. Shor, Multilayer grid embeddings for VLSI,
Algorithmica 6, pp. 129151 (1991).

P. W. Shor, Stretchability of pseudoline arrangements is NPhard, in
Applied Geometry and Discrete Mathematics: The Victor Klee
Festschrift (P. Gritzman & B. Sturmfels, eds.),
DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Vol. 4, American Math. Soc.,
Providence, RI, pp. 531554 (1991).

P. W. Shor and C. Van Wyk, Detecting and decomposing
selfoverlapping curves, Computational Geometry: Theory and
Applications 2, pp. 3150 (1992). Preliminary version:
5th ACM Symposium on Computational Geometry, pp. 4450 (1989).

M. Pellegrini and P. W. Shor, Finding stabbing lines in 3dimensional space,
Discrete and Computational Geometry 8, pp. 191208 (1992).
Preliminary version: Proc. 2nd ACMSIAM Symposium on Discrete
Algorithms, pp. 2431 (1991).

S. K. Rao, P. Sadayappan, F. K. Hwang and P. W. Shor, The rectilinear Steiner
arborescence problem, Algorithmica 7, 277288 (1992).

W. D. Smith and P. W. Shor, Steiner tree problems, Algorithmica
7, pp. 329332 (1992).

J. C. Lagarias and P. W. Shor, Keller's cubepacking conjecture is
false in high dimensions, Bull. AMS (New Series) 27,
279283 (1992).

J. C. Lagarias and P. W. Shor, Cube tilings of R^{n} and nonlinear
codes, Discrete and Computational Geometry 11, pp. 359391
(1994).

P. W. Shor and N. J. A. Sloane, A family of optimal packings in
Grassmannian manifolds, J. Algebraic Combinatorics 7,
pp. 157163 (1998).

A. R. Calderbank, R. H. Hardin, E. M. Rains, P. W. Shor and N. J. A. Sloane,
A grouptheoretic framework for the construction of packings in
Grassmannian spaces, J. Algebraic Combinatorics, to appear.

P. W. Shor, The averagecase analysis of some online algorithms for bin
packing, Combinatorica 6, pp. 179200 (1986).
Preliminary version: Proc. 25th Annual Symposium on Foundations of
Computer Science, IEEE Computer Society Press, pp. 193200 (1984).

T. Leighton and P. Shor, Tight bounds for minimax grid matching with
applications to the averagecase analysis of algorithms,
Combinatorica 9, pp. 161187 (1989). Preliminary version:
Proc. 18th Annual ACM Symposium on Theory of Computing, pp. 91103
(1986).

E. G. Coffman, Jr. and P. W. Shor, Averagecase analysis of cutting and
packing in two dimensions, European Journal of Operations Research
44,
pp. 134144 (1990).

P. W. Shor, How to pack better than Best Fit: Tight bounds for
averagecase online bin packing, Proc. 32nd Annual Symposium on
Foundations of Computer Science, pp. 752759 (1991).

E. G. Coffman, Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, L. A. McGeoch,
P. W. Shor, R. Weber and M. Yannakakis, Fundamental discrepancies
between averagecase analyses under discrete and continuous distributions:
A bin packing case study, Proc. 23rd Annual ACM Symp. on Theory of
Computing, pp. 230240 (1991).

E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and G. S. Lueker, Probabilistic
analysis of packing and related partitioning problems, Statistical
Science 8, 4047 (1993). Originally in:
Probability and Algorithms, National Research Council report,
National Academy Press (1992), pp. 87108.

J. Bramel, E. G. Coffman, Jr., P. W. Shor and D. SimchiLevi, Probabilistic
analysis of the capacitated vehicle routing problem with unsplit
demands, Operations Research 40, 10951106 (1992).

E. G. Coffman, Jr. and P. W. Shor, Packings in two dimensions: Asymptotic
averagecase analysis of algorithms, Algorithmica 9,
pp. 253277 (1993).

E. G. Coffman, Jr., D. S. Johnson, P. W. Shor, and R. R. Weber, Markov
chains, computer proofs, and averagecase analysis of best fit bin
packing, Proc. 25rd Annual ACM Symp. on Theory of Computing, pp. 412421 (1993).

E. G. Coffman, Jr., D. S. Johnson, P. W. Shor, and R. R. Weber,
Bin Packing with discrete item sizes, part II: Tight bounds on
First Fit, Random Structures and Algorithms 10,
pp. 69101 (1997).

J. L. Bruno, E. G. Coffman, Jr., J. C. Lagarias, T. J. Richardson and
P. W. Shor, Processor shadowing: Maximizing expected throughput in
faulttolerant systems, Mathematics of Operations Research,
23 pp. 257304 (1999).

E. G. Coffman, Jr. and P. W. Shor, A simple proof of the
$O\; (\; sqrt\; n\; log3/4n\; )$ upright
matching bound, SIAM J. Discrete Math.
4, pp. 4857 (1991).

P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures,
Annals of Probability, 19, 13381348 (1991).

E. G. Coffman, Jr., E. N. Gilbert, and P. W. Shor, A selectionreplacement
process on the circle, Annals of Applied Probability 3,
pp. 802818 (1993).

P. W. Shor, A lower bound on the length of a partial transversal in a Latin
square, J. Combinatorial Theory A 33, pp. 18 (1982).

D. B. West, W. T. Trotter, Jr., G. W. Peck and P. W. Shor, Regression and
monotone chains: A Ramseytype extremal problem for partial orders,
Combinatorica 4, pp. 117119 (1984).

J. F. Buss and P. W. Shor, On the pagenumber of planar graphs, Proc. 16th
Annual ACM Symposisum on Theory of Computing, pp. 98101 (1984).

P. W. Shor, A counterexample to the triangle conjecture, J. Combinatorial
Theory A 38, pp. 110112 (1985).

N. Linial, M. Saks and P. W. Shor, Largest induced suborders satisfying
the chain condition, Order 2, pp. 265268 (1985).

K. Collins, P. Shor and J. Stembridge, A lower bound for 0,1,* tournament
codes, Discrete Mathematics 63, pp. 1519 (1987).

R. J. Anderson, L. Lovasz, P. W. Shor, J. Spencer, E. Tardos and S. Winograd,
Disks, balls and walls: Analysis of a combinatorial game, American Math.
Monthly 96, pp. 481493 (1989).

A. Bjorner, L. Lovasz and P. W. Shor, Chipfiring games on graphs,
European J. Combinatorics 12, 283291 (1991).

P. W. Shor, A new proof of Cayley's formula for counting labeled trees,
J. Combinatorial Theory, Series A 71, pp. 154158 (1995).

J. Feigenbaum, D. Koller and P. W. Shor, A gametheoretic classification of
interactive complexity classes, Proc. 10th Annual Structures in Complexity
Theory Conference, IEEE Computer Society Press (1995), pp. 227237.

A. Condon, J. Feigenbaum, C. Lund and P. W. Shor, Probabilistically
checkable debate systems and approximation algorithms for PSPACEhard
functions, Chicago Journal of Theoretical Computer Science
1995, No. 4 (1995). Preliminary version:
Proc. 25rd Annual ACM Symp. on Theory of Computing,
pp. 305314 (1993).

A. Condon, J. Feigenbaum, C. Lund and P. W. Shor, Random debaters and
the hardness of approximating stochastic functions,
SIAM J. Computing 26, pp. 369400 (1997).
Preliminary version: Proc. 9th Annual
Structures in Complexity Theory Conference, IEEE Computer Society Press
(1994), pp. 280293.

F. Berman, D. Johnson, T. Leighton, P. W. Shor and L. Snyder, Generalized
planar matching, J. Algorithms 11 pp. 153184 (1990).

D. Bienstock, F. Chung, M. Fredman, A. A. Schaeffer, P. W. Shor and S. Suri,
A note on finding a strict saddlepoint, American Math. Monthly 98,
pp. 418419 (1991).

T. Leong, P. W. Shor and C. Stein, Implementation of a multicommodity
flow algorithm, in
Network Flows and Matching: First DIMACS Implementation Challenge
(D. S. Johnson and C. C. McGeoch, eds.),
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science Vol. 12,
American Math. Soc., Providence, RI (1993), pp. 387407.

M. Naor, A. Orlitsky and P. W. Shor, Three results on interactive
communication, IEEE Transactions on Information Theory 39,
pp. 16081615 (1993).

B. Berger, J. Rompel and P. W. Shor, Efficient NC algorithms for set cover
with applications to learning and geometry, J. Computer Systems Sci.
49, pp. 454477 (1994). Preliminary version: Proc. 30th Annual Symposium
on Foundations of Computer Science, IEEE Computer Society Press, pp. 5459
(1989).

B. A. Berger, P. W. Shor, L. TuckerKellogg and J. King, A local rule
based theory of virus shell assembly, Proc. National Academy
Sciences U.S.A. 91, (1994), pp. 77327736.

B. A. Berger and P. W. Shor, Tight bounds for the acyclic
subgraph problem, J. Algorithms 25, pp. 118 (1997).
Preliminary version:
Proc. 1st ACMSIAM Symposium on Discrete Algorithms,
pp. 236243 (1990).

B. A. Berger and P. W. Shor, On the structure of the scaffolding
core of bacteriophage T4 and its role in head length determination
J. Structural Biology 121, (1998), to appear.

P. W. Shor, Problem 786: A combinatorial identity,
in Problems and Solutions column, SIAM Review; problem in 20, p. 394 (1978);
solution in 21, pp. 258260 (1979).

P. W. Shor, Monthly problem 10408, in
Problems and Solutions column (R. Bumby, ed.),
American Math. Monthly 101, p. 793 (1994).

P. W. Shor, Analog computational power, technical comment,
Science 271, p. 92 (1996).
Out to my homepage.