Publication List

Last Updated: Woefully out of date



I have divided my publications list into the following categories:
quantum computing, geometry,
bin packing and scheduling, probability,
combinatorics, complexity,
other technical papers miscellaneous stuff.

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 quant-ph preprint archive.

Quantum Computing

  1. 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), 124-134.
  2. P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52, pp. 2493-2496 (1995).
  3. 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. 3457-3467 (1995).
  4. I. L. Chuang, R. Laflamme, P. W. Shor and W. H. Zurek, Quantum computers, factoring and decoherence, Science, 270, pp. 1635-1637 (1995).
  5. A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54, pp. 1098-1106 (1996).
  6. D. P. DiVincenzo and P. W. Shor, Fault tolerant error correction with efficient quantum codes, Phys. Rev. Lett. 77, pp. 3260-3263 (1996).
  7. P. W. Shor, Fault-tolerant quantum computation, Proc. 37nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp. 56-65 (1996).
  8. A. R. Calderbank, E. Rains, P. W. Shor and N. J. A. Sloane, Quantum error correction and orthogonal geometry, Phys. Rev. Lett. 78, pp. 405-408 (1997).
  9. P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 26, pp. 1484-1509 (1997).
  10. P. Shor and R. Laflamme, Quantum analog of the MacWilliams identities in classical coding theory, Phys. Rev. Lett. 78, pp. 1600-1603 (1997).
  11. E. M. Rains, R. H. Hardin, P. W. Shor and N. J. A. Sloane, A nonadditive quantum code, Phys. Rev. Lett. 79, pp. 953-954 (1997).
  12. D. P. DiVincenzo, P. W. Shor and J. A. Smolin, Quantum-channel capacity of very noisy channels Phys. Rev. A. 57 pp. 830-839 (1998).
  13. 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.

Discrete and Computational Geometry:

  1. A. Aggarwal, M. Klawe, S. Moran, P. Shor and R. Wilber, Geometric applications of a matrix searching algorithm, Algorithmica 2, pp. 195-208 (1987). Preliminary version: Proc. 2nd ACM Annual Symposium on Computational Geometry, pp. 285-292 (1986).
  2. 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. 591-604 (1989). Preliminary version: Proc. 19th Annual ACM Symposium on Theory of Computing, pp. 39-45 (1987).
  3. K. L. Clarkson and P. W. Shor, Applications of randomization in computational geometry II, Discrete and Computational Geometry 4, pp. 387-421 (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. 12-17 (1988).
  4. 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, Springer-Verlag, pp. 115-119 (1989).
  5. P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, J. Combinatorial Theory A 52, pp. 228-274 (1989).
  6. A. Aggarwal, M. Klawe and P. Shor, Multi-layer grid embeddings for VLSI, Algorithmica 6, pp. 129-151 (1991).
  7. P. W. Shor, Stretchability of pseudoline arrangements is NP-hard, 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. 531-554 (1991).
  8. P. W. Shor and C. Van Wyk, Detecting and decomposing self-overlapping curves, Computational Geometry: Theory and Applications 2, pp. 31-50 (1992). Preliminary version: 5th ACM Symposium on Computational Geometry, pp. 44-50 (1989).
  9. M. Pellegrini and P. W. Shor, Finding stabbing lines in 3-dimensional space, Discrete and Computational Geometry 8, pp. 191-208 (1992). Preliminary version: Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, pp. 24-31 (1991).
  10. S. K. Rao, P. Sadayappan, F. K. Hwang and P. W. Shor, The rectilinear Steiner arborescence problem, Algorithmica 7, 277-288 (1992).
  11. W. D. Smith and P. W. Shor, Steiner tree problems, Algorithmica 7, pp. 329-332 (1992).
  12. J. C. Lagarias and P. W. Shor, Keller's cube-packing conjecture is false in high dimensions, Bull. AMS (New Series) 27, 279-283 (1992).
  13. J. C. Lagarias and P. W. Shor, Cube tilings of Rn and nonlinear codes, Discrete and Computational Geometry 11, pp. 359-391 (1994).
  14. P. W. Shor and N. J. A. Sloane, A family of optimal packings in Grassmannian manifolds, J. Algebraic Combinatorics 7, pp. 157-163 (1998).
  15. A. R. Calderbank, R. H. Hardin, E. M. Rains, P. W. Shor and N. J. A. Sloane, A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Combinatorics, to appear.

Bin Packing and Scheduling

  1. P. W. Shor, The average-case analysis of some on-line algorithms for bin packing, Combinatorica 6, pp. 179-200 (1986). Preliminary version: Proc. 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp. 193-200 (1984).
  2. T. Leighton and P. Shor, Tight bounds for minimax grid matching with applications to the average-case analysis of algorithms, Combinatorica 9, pp. 161-187 (1989). Preliminary version: Proc. 18th Annual ACM Symposium on Theory of Computing, pp. 91-103 (1986).
  3. E. G. Coffman, Jr. and P. W. Shor, Average-case analysis of cutting and packing in two dimensions, European Journal of Operations Research 44, pp. 134-144 (1990).
  4. P. W. Shor, How to pack better than Best Fit: Tight bounds for average-case on-line bin packing, Proc. 32nd Annual Symposium on Foundations of Computer Science, pp. 752-759 (1991).
  5. 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 average-case analyses under discrete and continuous distributions: A bin packing case study, Proc. 23rd Annual ACM Symp. on Theory of Computing, pp. 230-240 (1991).
  6. 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, 40-47 (1993). Originally in: Probability and Algorithms, National Research Council report, National Academy Press (1992), pp. 87-108.
  7. J. Bramel, E. G. Coffman, Jr., P. W. Shor and D. Simchi-Levi, Probabilistic analysis of the capacitated vehicle routing problem with unsplit demands, Operations Research 40, 1095-1106 (1992).
  8. E. G. Coffman, Jr. and P. W. Shor, Packings in two dimensions: Asymptotic average-case analysis of algorithms, Algorithmica 9, pp. 253-277 (1993).
  9. E. G. Coffman, Jr., D. S. Johnson, P. W. Shor, and R. R. Weber, Markov chains, computer proofs, and average-case analysis of best fit bin packing, Proc. 25rd Annual ACM Symp. on Theory of Computing, pp. 412-421 (1993).
  10. 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. 69-101 (1997).
  11. J. L. Bruno, E. G. Coffman, Jr., J. C. Lagarias, T. J. Richardson and P. W. Shor, Processor shadowing: Maximizing expected throughput in fault-tolerant systems, Mathematics of Operations Research, 23 pp. 257-304 (1999).

Applied Probability

  1. E. G. Coffman, Jr. and P. W. Shor, A simple proof of the O ( sqrt n log 3/4 n ) upright matching bound, SIAM J. Discrete Math. 4, pp. 48-57 (1991).
  2. P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, Annals of Probability, 19, 1338-1348 (1991).
  3. E. G. Coffman, Jr., E. N. Gilbert, and P. W. Shor, A selection-replacement process on the circle, Annals of Applied Probability 3, pp. 802-818 (1993).

Combinatorics

  1. P. W. Shor, A lower bound on the length of a partial transversal in a Latin square, J. Combinatorial Theory A 33, pp. 1-8 (1982).
  2. D. B. West, W. T. Trotter, Jr., G. W. Peck and P. W. Shor, Regression and monotone chains: A Ramsey-type extremal problem for partial orders, Combinatorica 4, pp. 117-119 (1984).
  3. J. F. Buss and P. W. Shor, On the pagenumber of planar graphs, Proc. 16th Annual ACM Symposisum on Theory of Computing, pp. 98-101 (1984).
  4. P. W. Shor, A counterexample to the triangle conjecture, J. Combinatorial Theory A 38, pp. 110-112 (1985).
  5. N. Linial, M. Saks and P. W. Shor, Largest induced suborders satisfying the chain condition, Order 2, pp. 265-268 (1985).
  6. K. Collins, P. Shor and J. Stembridge, A lower bound for 0,1,* tournament codes, Discrete Mathematics 63, pp. 15-19 (1987).
  7. 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. 481-493 (1989).
  8. A. Bjorner, L. Lovasz and P. W. Shor, Chip-firing games on graphs, European J. Combinatorics 12, 283-291 (1991).
  9. P. W. Shor, A new proof of Cayley's formula for counting labeled trees, J. Combinatorial Theory, Series A 71, pp. 154-158 (1995).

Computational Complexity Theory

  1. J. Feigenbaum, D. Koller and P. W. Shor, A game-theoretic classification of interactive complexity classes, Proc. 10th Annual Structures in Complexity Theory Conference, IEEE Computer Society Press (1995), pp. 227-237.
  2. A. Condon, J. Feigenbaum, C. Lund and P. W. Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Chicago Journal of Theoretical Computer Science 1995, No. 4 (1995). Preliminary version: Proc. 25rd Annual ACM Symp. on Theory of Computing, pp. 305-314 (1993).
  3. A. Condon, J. Feigenbaum, C. Lund and P. W. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM J. Computing 26, pp. 369-400 (1997). Preliminary version: Proc. 9th Annual Structures in Complexity Theory Conference, IEEE Computer Society Press (1994), pp. 280-293.

Other Technical Papers

  1. F. Berman, D. Johnson, T. Leighton, P. W. Shor and L. Snyder, Generalized planar matching, J. Algorithms 11 pp. 153-184 (1990).
  2. 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. 418-419 (1991).
  3. 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. 387-407.
  4. M. Naor, A. Orlitsky and P. W. Shor, Three results on interactive communication, IEEE Transactions on Information Theory 39, pp. 1608-1615 (1993).
  5. 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. 454-477 (1994). Preliminary version: Proc. 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp. 54-59 (1989).
  6. B. A. Berger, P. W. Shor, L. Tucker-Kellogg and J. King, A local rule based theory of virus shell assembly, Proc. National Academy Sciences U.S.A. 91, (1994), pp. 7732-7736.
  7. B. A. Berger and P. W. Shor, Tight bounds for the acyclic subgraph problem, J. Algorithms 25, pp. 1-18 (1997). Preliminary version: Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, pp. 236-243 (1990).
  8. 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.

Problems and Comments

  1. P. W. Shor, Problem 78-6: A combinatorial identity, in Problems and Solutions column, SIAM Review; problem in 20, p. 394 (1978); solution in 21, pp. 258-260 (1979).
  2. P. W. Shor, Monthly problem 10408, in Problems and Solutions column (R. Bumby, ed.), American Math. Monthly 101, p. 793 (1994).
  3. P. W. Shor, Analog computational power, technical comment, Science 271, p. 92 (1996).



Out to my homepage.