Arrow Research search

Author name cluster

Peter W. Shor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
1 author row

Possible papers

15

SODA Conference 2011 Conference Paper

A complete resolution of the Keller maximum clique problem

  • Jennifer Debroni
  • John D. Eblen
  • Michael A. Langston
  • Wendy J. Myrvold
  • Peter W. Shor
  • Dinesh Weerapurage

A d -dimensional Keller graph has vertices which are numbered with each of the 4 d possible d-digit numbers ( d -tuples) which have each digit equal to 0, 1, 2, or 3. Two vertices are adjacent if their labels differ in at least two positions, and in at least one position the difference in the labels is two modulo four. Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms. The dimension seven case was the last remaining Keller graph for which the maximum clique order was not known. It has been claimed in order to resolve this last case it might take a “high speed computer the size of a major galaxy”. This paper describes the computation we used to determine that the maximum clique order for dimension seven is 124.

Details

FOCS Conference 1996 Conference Paper

Fault-Tolerant Quantum Computation

  • Peter W. Shor

It has recently been realized that use of the properties of quantum mechanics might speed up certain computations dramatically. Interest in quantum computation has since been growing. One of the main difficulties in realizing quantum computation is that decoherence tends to destroy the information in a superposition of states in a quantum computer making long computations impossible. A further difficulty is that inaccuracies in quantum state transformations throughout the computation accumulate, rendering long computations unreliable. However, these obstacles may not be as formidable as originally believed. For any quantum computation with t gates, we show how to build a polynomial size quantum circuit that tolerates O(1/log/sup c/t) amounts of inaccuracy and decoherence per gate, for some constant c; the previous bound was O(1/t). We do this by showing that operations can be performed on quantum data encoded by quantum error-correcting codes without decoding this data.

Details

FOCS Conference 1994 Conference Paper

Algorithms for Quantum Computation: Discrete Logarithms and Factoring

  • Peter W. Shor

A computer is generally considered to be a universal computational device; i. e. , it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e. g. , the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis. >

Details

FOCS Conference 1991 Conference Paper

How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing

  • Peter W. Shor

An O(n log n)-time online algorithm is given for packing items i. i. d. uniform on (0, 1) into bins of size 1 with expected wasted space Theta (n/sup 1/2/ log /sup 1/2/n). This matches the lowest bound that no online algorithm can achieve O(n/sup 1/2/ log /sup 1/2/ n) wasted space. It is done by analyzing another algorithm which involves putting balls into buckets online. The analysis of this second algorithm also gives bound on the stochastic rightward matching problem, which arises in analyzing not only the above online bin packing problem, but also a 2-D problem of packing rectangles into a half-infinite strip. The bounds on rightward matching thus give good bounds for the 2-D strip packing problem. >

Details

FOCS Conference 1989 Conference Paper

Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry

  • Bonnie Berger
  • John Rompel
  • Peter W. Shor

NC approximation algorithms are given for the unweighted and weighted set cover problems. The algorithms use a linear number of processors and give a cover that has at most log n times the optimal size/weight, thus matching the performance of the best sequential algorithms. The set cover algorithm is applied to learning theory, providing an NC algorithm for learning the concept class obtained by taking the closure under finite union or finite intersection of any concept class of finite VC dimension which has an NC hypothesis finder. In addition, a linear-processor NC algorithm is given for a variant of the set cover problem and used to obtain NC algorithms for several problems in computational geometry. >

Details

STOC Conference 1987 Conference Paper

A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon

  • Alok Aggarwal
  • Leonidas J. Guibas
  • James B. Saxe
  • Peter W. Shor

We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n points in the plane can be computed in Θ( n ) time when these points form the vertices of a convex polygon in, say, counterclockwise order. This settles an outstanding open problem in computational geometry. Our techniques can also be used to obtain linear time algorithms for computing the farthest-point Voronoi diagram and the medial axis of a convex polygon and for deleting a vertex from a general planar Voronoi diagram.

Details

FOCS Conference 1984 Conference Paper

The Average-Case Analysis of Some On-Line Algorithms for Bin Packing

  • Peter W. Shor

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Bets Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm. These results are proven by analyzing problems concerning matching random points in a unit square. We give a new lower bound for upward right matching and grid matching.

Details
v2026.09.13