Peter W. Shor

According to our database, Peter W. Shor authored at least 93 papers between 1982 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension k Codes.

Robert Lin, Peter W. Shor

CoRR, 2024

2023

Bounding the Forward Classical Capacity of Bipartite Quantum Channels.

Dawei Ding, Sumeet Khatri, Yihui Quek, Peter W. Shor, Xin Wang, Mark M. Wilde

IEEE Trans. Inf. Theory, May, 2023

2021

Upper bound on the classical capacity of a quantum channel assisted by classical feedback.

Dawei Ding, Sumeet Khatri, Yihui Quek, Peter W. Shor, Xin Wang, Mark M. Wilde

Proceedings of the IEEE International Symposium on Information Theory, 2021

2019

Superadditivity in Trade-Off Capacities of Quantum Channels.

Elton Yechao Zhu, Quntao Zhuang, Min-Hsiu Hsieh, Peter W. Shor

IEEE Trans. Inf. Theory, 2019

Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel.

Seth Lloyd, Peter W. Shor, Kevin Thompson

IEEE Trans. Inf. Theory, 2019

Entropy Bound for the Classical Capacity of a Quantum Channel Assisted by Classical Feedback.

Dawei Ding, Yihui Quek, Peter W. Shor, Mark M. Wilde

Proceedings of the IEEE International Symposium on Information Theory, 2019

2017

Superadditivity of the classical capacity with limited entanglement assistance.

Elton Yechao Zhu, Quntao Zhuang, Peter W. Shor

CoRR, 2017

Quantum and Super-quantum enhancements to two-sender, two-receiver channels.

Yihui Quek, Peter W. Shor

CoRR, 2017

2016

The Systematic Normal Form of Lattices.

Lior Eldar, Peter W. Shor

CoRR, 2016

2015

New Constructions of Codes for Asymmetric Channels via Concatenation.

Markus Grassl, Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng

IEEE Trans. Inf. Theory, 2015

Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH.

Mohammad Bavarian, Peter W. Shor

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating Quantum Channels.

Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas J. Winter

IEEE Trans. Inf. Theory, 2014

A new relativistic orthogonal states quantum key distribution protocol.

Jordan S. Cotler, Peter W. Shor

Quantum Inf. Comput., 2014

2012

Quantum money from knots.

Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Quantum Interactive Proofs with Short Messages.

Salman Beigi, Peter W. Shor, John Watrous

Theory Comput., 2011

High Performance Single-Error-Correcting Quantum Codes for Amplitude Damping.

Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng

IEEE Trans. Inf. Theory, 2011

Unstructured randomness, small gaps and localization.

Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Peter W. Shor

Quantum Inf. Comput., 2011

Quantum adiabatic algorithms, small gaps, and different paths.

Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, Peter W. Shor

Quantum Inf. Comput., 2011

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

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Time reversal and exchange symmetries of unitary gate capacities.

Aram W. Harrow, Peter W. Shor

IEEE Trans. Inf. Theory, 2010

Questions answered. in theory.: http://cstheory.stackexchange.com/.

Dave Clarke, David Eppstein, Kaveh Ghasemloo, Lev Reyzin, András Z. Salamon, Peter W. Shor, Aaron D. Sterling, Suresh Venkatasubramanian

SIGACT News, 2010

C_3, semi-Clifford and genralized semi-Clifford operations.

Salman Beigi, Peter W. Shor

Quantum Inf. Comput., 2010

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol.

Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor

Proceedings of the Innovations in Computer Science, 2010

2009

The Power of Unentanglement.

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor

Theory Comput., 2009

Quantum Reverse Shannon Theorem.

Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas J. Winter

CoRR, 2009

Generalized concatenation for quantum codes.

Markus Grassl, Peter W. Shor, Bei Zeng

Proceedings of the IEEE International Symposium on Information Theory, 2009

2008

Channel-Adapted Quantum Error Correction for the Amplitude Damping Channel.

Andrew S. Fletcher, Peter W. Shor, Moe Z. Win

IEEE Trans. Inf. Theory, 2008

Estimating Jones polynomials is a complete problem for one clean qubit.

Peter W. Shor, Stephen P. Jordan

Quantum Inf. Comput., 2008

Entanglement purification with two-way classical communication.

Alan W. Leung, Peter W. Shor

Quantum Inf. Comput., 2008

Random Quantum Codes from Gaussian Ensembles and an Uncertainty Relation.

Patrick M. Hayden, Peter W. Shor, Andreas J. Winter

Open Syst. Inf. Dyn., 2008

A lower bound for the length of a partial transversal in a Latin square.

Pooya Hatami, Peter W. Shor

J. Comb. Theory, Ser. A, 2008

2006

On the Sum-of-Squares algorithm for bin packing.

János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber

J. ACM, 2006

2005

Remote preparation of quantum states.

Charles H. Bennett, Patrick M. Hayden, Debbie W. Leung, Peter W. Shor, Andreas J. Winter

IEEE Trans. Inf. Theory, 2005

2004

Progress in Quantum Algorithms.

Peter W. Shor

Quantum Inf. Process., 2004

The classical capacity achievable by a quantum channel assisted by a limited entanglement.

Peter W. Shor

Quantum Inf. Comput., 2004

The adaptive classical capacity of a quantum channel, or Information capacities of three symmetric pure states in three dimensions.

Peter W. Shor

IBM J. Res. Dev., 2004

2003

Capacities of quantum channels and how to find them.

Peter W. Shor

Math. Program., 2003

Why haven't more quantum algorithms been found?.

Peter W. Shor

J. ACM, 2003

The Cutting-Stock Approach to Bin Packing: Theory and Experiments.

David L. Applegate, Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor

Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002

Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem.

Charles H. Bennett, Peter W. Shor, John A. Smolin, Ashish V. Thapliyal

IEEE Trans. Inf. Theory, 2002

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.

Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM Rev., 2002

2000

Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM J. Discret. Math., 2000

Local rule mechanism for selecting icosahedral shell geometry.

Bonnie Berger, Jonathan A. King, Russell Schwartz, Peter W. Shor

Discret. Appl. Math., 2000

1999

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.

Peter W. Shor

SIAM Rev., 1999

Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems.

John L. Bruno, Edward G. Coffman Jr., Jeffrey C. Lagarias, Tom J. Richardson, Peter W. Shor

Math. Oper. Res., 1999

On the Structure of the Scaffolding Core of Bacteriophage T4.

Bonnie Berger, G. W. Hoest, J. R. Paulson, Peter W. Shor

J. Comput. Biol., 1999

A Self Organizing Bin Packing Heuristic.

János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber

Proceedings of the Algorithm Engineering and Experimentation, 1999

1998

Quantum Error Correction Via Codes Over GF(4).

A. Robert Calderbank, Eric M. Rains, Peter W. Shor, Neil J. A. Sloane

IEEE Trans. Inf. Theory, 1998

Quantum Information Theory.

Charles H. Bennett, Peter W. Shor

IEEE Trans. Inf. Theory, 1998

1997

Random Debaters and the Hardness of Approximating Stochastic Functions.

Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor

SIAM J. Comput., 1997

Bin packing with discrete item sizes, part II: Tight bounds on First Fit.

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber

Random Struct. Algorithms, 1997

Tight Bounds for the Maximum Acyclic Subgraph Problem.

Bonnie Berger, Peter W. Shor

J. Algorithms, 1997

1996

Fault-Tolerant Quantum Computation.

Peter W. Shor

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

A New Proof of Cayley's Formula for Counting Labeled Trees.

Peter W. Shor

J. Comb. Theory, Ser. A, 1995

Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.

Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor

Chic. J. Theor. Comput. Sci., 1995

A Game-Theoretic Classification of Interactive Complexity Classes.

Joan Feigenbaum, Daphne Koller, Peter W. Shor

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

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

Bonnie Berger, John Rompel, Peter W. Shor

J. Comput. Syst. Sci., 1994

Cube-Tilings of Rⁿ and Nonlinear Codes.

J. C. Lagarias, Peter W. Shor

Discret. Comput. Geom., 1994

Algorithms for Quantum Computation: Discrete Logarithms and Factoring

Peter W. Shor

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Polynominal time algorithms for discrete logarithms and factoring on a quantum computer.

Peter W. Shor

Proceedings of the Algorithmic Number Theory, First International Symposium, 1994

1993

Three results on interactive communication.

Moni Naor, Alon Orlitsky, Peter W. Shor

IEEE Trans. Inf. Theory, 1993

Packings in Two Dimensions: Asymptotic Average-Case Analysis of Algorithms.

Edward G. Coffman Jr., Peter W. Shor

Algorithmica, 1993

Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions.

Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Markov chains, computer proofs, and average-case analysis of best fit bin packing.

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands.

Julien Bramel, Edward G. Coffman Jr., Peter W. Shor, David Simchi-Levi

Oper. Res., 1992

Finding Stabbing Lines in 3-Space.

Marco Pellegrini, Peter W. Shor

Discret. Comput. Geom., 1992

Detecting and Decomposing Self-overlapping Curves.

Peter W. Shor, Christopher J. Van Wyk

Comput. Geom., 1992

Steiner Tree Problems.

Warren D. Smith, Peter W. Shor

Algorithmica, 1992

The Rectilinear Steiner Arborescence Problem.

Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor

Algorithmica, 1992

1991

A Simple Proof of the <i>O</i>(sqrt(n log^3/4 <i>n</i>) Upright Matching Bound.

Edward G. Coffman Jr., Peter W. Shor

SIAM J. Discret. Math., 1991

Chip-firing Games on Graphs.

Anders Björner, László Lovász, Peter W. Shor

Eur. J. Comb., 1991

Multilayer Grid Embeddings for VLSI.

Alok Aggarwal, Maria M. Klawe, Peter W. Shor

Algorithmica, 1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Finding Stabbing Lines in 3-Dimensional Space.

Marco Pellegrini, Peter W. Shor

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

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

Peter W. Shor

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Implementation of a Combinatorial Multicommodity Flow Algorithm.

Tishya Leong, Peter W. Shor, Clifford Stein

Proceedings of the Network Flows And Matching, 1991

1990

Generalized Planar Matching.

Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder

J. Algorithms, 1990

Approximation Algorithms for the Maximum Acyclic Subgraph Problem.

Bonnie Berger, Peter W. Shor

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Stretchability of Pseudolines is NP-Hard.

Peter W. Shor

Proceedings of the Applied Geometry And Discrete Mathematics, 1990

1989

Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.

Pankaj K. Agarwal, Micha Sharir, Peter W. Shor

J. Comb. Theory, Ser. A, 1989

Application of Random Sampling in Computational Geometry, II.

Kenneth L. Clarkson, Peter W. Shor

Discret. Comput. Geom., 1989

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

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

Discret. Comput. Geom., 1989

Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms.

Tom Leighton, Peter W. Shor

Comb., 1989

Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version).

Alok Aggarwal, Shlomo Moran, Peter W. Shor, Subhash Suri

Proceedings of the Algorithms and Data Structures, 1989

1988

Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental.

Kenneth L. Clarkson, Peter W. Shor

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987

A lower bound for 0, 1, * tournament codes.

Karen L. Collins, Peter W. Shor, John R. Stembridge

Discret. Math., 1987

Geometric Applications of a Matrix-Searching Algorithm.

Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, Robert E. Wilber

Algorithmica, 1987

1986

the average-case analysis of some on-line algorithms for bin packing.

Peter W. Shor

Comb., 1986

Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms

Frank Thomson Leighton, Peter W. Shor

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

A Counterexample to the Triangle Conjecture.

Peter W. Shor

J. Comb. Theory, Ser. A, 1985

1984

Regressions and monotone chains: a ramsey - type extermal problem for partial orders.

Douglas B. West, William T. Trotter, G. W. Peck, Peter W. Shor

Comb., 1984

On the Pagenumber of Planar Graphs

Jonathan F. Buss, Peter W. Shor

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1982

A Lower Bound for the Length of a Partial Transversal in a Latin Square.

Peter W. Shor

J. Comb. Theory, Ser. A, 1982