Peter W. Shor

120 papers A* 16A 7B 6Journal 83Unranked 8
YearRankTypeTitle / Venue / Authors
2026 A conf
The Learning Stabilizers with Noise Problem.
ITCS
Alexander Poremba, Yihui Quek, Peter W. Shor
2024 J jnl
A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension k Codes.
CoRR
Robert Lin, Peter W. Shor
2024 J jnl
Maximizing Free Energy Gain.
Entropy
Artemy Kolchinsky, Iman Marvian, Can Gokler, Zi-Wen Liu, Peter W. Shor, Oles Shtanko, Kevin Thompson, David H. Wolpert, Seth Lloyd
2024 J jnl
The Learning Stabilizers with Noise problem.
CoRR
Alexander Poremba, Yihui Quek, Peter W. Shor
2024 J jnl
The Learning Stabilizers with Noise problem.
IACR Cryptol. ePrint Arch.
Alexander Poremba, Yihui Quek, Peter W. Shor
2023 J jnl
Bounding the Forward Classical Capacity of Bipartite Quantum Channels.
IEEE Trans. Inf. Theory
Dawei Ding, Sumeet Khatri, Yihui Quek, Peter W. Shor, Xin Wang, Mark M. Wilde
2021 B conf
Upper bound on the classical capacity of a quantum channel assisted by classical feedback.
ISIT
Dawei Ding, Sumeet Khatri, Yihui Quek, Peter W. Shor, Xin Wang, Mark M. Wilde
2020 J jnl
Bounding the forward classical capacity of bipartite quantum channels.
CoRR
Dawei Ding, Sumeet Khatri, Yihui Quek, Peter W. Shor, Xin Wang, Mark M. Wilde
2019 B conf
Entropy Bound for the Classical Capacity of a Quantum Channel Assisted by Classical Feedback.
ISIT
Dawei Ding, Yihui Quek, Peter W. Shor, Mark M. Wilde
2019 J jnl
Entropy Bound for the Classical Capacity of a Quantum Channel Assisted by Classical Feedback.
CoRR
Dawei Ding, Yihui Quek, Peter W. Shor, Mark M. Wilde
2019 J jnl
Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel.
IEEE Trans. Inf. Theory
Seth Lloyd, Peter W. Shor, Kevin Thompson
2019 J jnl
Superadditivity in Trade-Off Capacities of Quantum Channels.
IEEE Trans. Inf. Theory
Elton Yechao Zhu, Quntao Zhuang, Min-Hsiu Hsieh, Peter W. Shor
2018 B conf
Superadditivity in Trade-Off Capacities of Quantum Channels.
ISIT
Elton Yechao Zhu, Quntao Zhuang, Min-Hsiu Hsieh, Peter W. Shor
2017 J jnl
Quantum and Super-quantum enhancements to two-sender, two-receiver channels.
CoRR
Yihui Quek, Peter W. Shor
2017 J jnl
Superadditivity in trade-off capacities of quantum channels.
CoRR
Elton Yechao Zhu, Quntao Zhuang, Min-Hsiu Hsieh, Peter W. Shor
2017 J jnl
Superadditivity of the classical capacity with limited entanglement assistance.
CoRR
Elton Yechao Zhu, Quntao Zhuang, Peter W. Shor
2016 J jnl
The Systematic Normal Form of Lattices.
CoRR
Lior Eldar, Peter W. Shor
2015 A conf
Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH.
ITCS
Mohammad Bavarian, Peter W. Shor
2015 J jnl
New Constructions of Codes for Asymmetric Channels via Concatenation.
IEEE Trans. Inf. Theory
Markus Grassl, Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng
2014 J jnl
A new relativistic orthogonal states quantum key distribution protocol.
Quantum Inf. Comput.
Jordan S. Cotler, Peter W. Shor
2014 J jnl
The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating Quantum Channels.
IEEE Trans. Inf. Theory
Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas J. Winter
2013 J jnl
Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH.
CoRR
Mohammad Bavarian, Peter W. Shor
2013 J jnl
New Constructions of Codes for Asymmetric Channels via Concatenation.
CoRR
Markus Grassl, Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng
2012 B conf
New constructions of codes for asymmetric channels via concatenation.
ISIT
Markus Grassl, Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng
2012 A conf
Quantum money from knots.
ITCS
Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor
2011 A* conf
A complete resolution of the Keller maximum clique problem.
SODA
Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy J. Myrvold, Peter W. Shor, Dinesh Weerapurage
2011 J jnl
High Performance Single-Error-Correcting Quantum Codes for Amplitude Damping.
IEEE Trans. Inf. Theory
Peter W. Shor, Graeme Smith, John A. Smolin, Bei Zeng
2011 J jnl
Quantum Interactive Proofs with Short Messages.
Theory Comput.
Salman Beigi, Peter W. Shor, John Watrous
2011 J jnl
Quantum adiabatic algorithms, small gaps, and different paths.
Quantum Inf. Comput.
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, Peter W. Shor
2011 J jnl
Unstructured randomness, small gaps and localization.
Quantum Inf. Comput.
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Peter W. Shor
2010 A conf
Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol.
ICS
Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor
2010 J jnl
C_3, semi-Clifford and genralized semi-Clifford operations.
Quantum Inf. Comput.
Salman Beigi, Peter W. Shor
2010 J jnl
Quantum interactive proofs with short messages
CoRR
Salman Beigi, Peter W. Shor, John Watrous
2010 J jnl
Quantum money from knots
CoRR
Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor
2010 J jnl
Questions answered. in theory.: http://cstheory.stackexchange.com/.
SIGACT News
Dave Clarke, David Eppstein, Kaveh Ghasemloo, Lev Reyzin, András Z. Salamon, Peter W. Shor, Aaron D. Sterling, Suresh Venkatasubramanian
2010 J jnl
Time reversal and exchange symmetries of unitary gate capacities.
IEEE Trans. Inf. Theory
Aram W. Harrow, Peter W. Shor
2009 B conf
Generalized concatenation for quantum codes.
ISIT
Markus Grassl, Peter W. Shor, Bei Zeng
2009 J jnl
Quantum Adiabatic Algorithms, Small Gaps, and Different Paths
CoRR
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, Peter W. Shor
2009 J jnl
Quantum Reverse Shannon Theorem.
CoRR
Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas J. Winter
2009 J jnl
The Power of Unentanglement.
Theory Comput.
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008 J jnl
A lower bound for the length of a partial transversal in a Latin square.
J. Comb. Theory A
Pooya Hatami, Peter W. Shor
2008 J jnl
Channel-Adapted Quantum Error Correction for the Amplitude Damping Channel.
IEEE Trans. Inf. Theory
Andrew S. Fletcher, Peter W. Shor, Moe Z. Win
2008 J jnl
Entanglement purification with two-way classical communication.
Quantum Inf. Comput.
Alan W. Leung, Peter W. Shor
2008 J jnl
Estimating Jones polynomials is a complete problem for one clean qubit.
Quantum Inf. Comput.
Peter W. Shor, Stephen P. Jordan
2008 J jnl
Random Quantum Codes from Gaussian Ensembles and an Uncertainty Relation.
Open Syst. Inf. Dyn.
Patrick M. Hayden, Peter W. Shor, Andreas J. Winter
2008 A conf
The Power of Unentanglement.
CCC
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008 J jnl
The Power of Unentanglement.
Electron. Colloquium Comput. Complex.
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2007 J jnl
Random quantum codes from Gaussian ensembles and an uncertainty relation.
CoRR
Patrick M. Hayden, Peter W. Shor, Andreas J. Winter
2006 J jnl
On the Sum-of-Squares algorithm for bin packing.
J. ACM
János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
2005 J jnl
Remote preparation of quantum states.
IEEE Trans. Inf. Theory
Charles H. Bennett, Patrick M. Hayden, Debbie W. Leung, Peter W. Shor, Andreas J. Winter
2004 J jnl
Progress in Quantum Algorithms.
Quantum Inf. Process.
Peter W. Shor
2004 J jnl
The adaptive classical capacity of a quantum channel, or Information capacities of three symmetric pure states in three dimensions.
IBM J. Res. Dev.
Peter W. Shor
2004 J jnl
The classical capacity achievable by a quantum channel assisted by a limited entanglement.
Quantum Inf. Comput.
Peter W. Shor
2003 J jnl
Capacities of quantum channels and how to find them.
Math. Program.
Peter W. Shor
2003 A conf
The Cutting-Stock Approach to Bin Packing: Theory and Experiments.
ALENEX
David L. Applegate, Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor
2003 J jnl
Why haven't more quantum algorithms been found?.
J. ACM
Peter W. Shor
2002 J jnl
Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem.
IEEE Trans. Inf. Theory
Charles H. Bennett, Peter W. Shor, John A. Smolin, Ashish V. Thapliyal
2002 J jnl
On the Sum-of-Squares Algorithm for Bin Packing
CoRR
János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
2002 J jnl
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Rev.
Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
2000 J jnl
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discret. Math.
Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
2000 J jnl
Local rule mechanism for selecting icosahedral shell geometry.
Discret. Appl. Math.
Bonnie Berger, Jonathan A. King, Russell Schwartz, Peter W. Shor
2000 A* conf
On the sum-of-squares algorithm for bin packing.
STOC
János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
1999 A conf
A Self Organizing Bin Packing Heuristic.
ALENEX
János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
1999 J jnl
On the Structure of the Scaffolding Core of Bacteriophage T4.
J. Comput. Biol.
Bonnie Berger, G. W. Hoest, J. R. Paulson, Peter W. Shor
1999 J jnl
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
SIAM Rev.
Peter W. Shor
1999 J jnl
Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems.
Math. Oper. Res.
John L. Bruno, Edward G. Coffman Jr., Jeffrey C. Lagarias, Tom J. Richardson, Peter W. Shor
1998 J jnl
Quantum Error Correction Via Codes Over GF(4).
IEEE Trans. Inf. Theory
A. Robert Calderbank, Eric M. Rains, Peter W. Shor, Neil J. A. Sloane
1998 J jnl
Quantum Information Theory.
IEEE Trans. Inf. Theory
Charles H. Bennett, Peter W. Shor
1997 J jnl
Bin packing with discrete item sizes, part II: Tight bounds on First Fit.
Random Struct. Algorithms
Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber
1997 J jnl
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
SIAM J. Comput.
Peter W. Shor
1997 A* ed.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997
STOC
Frank Thomson Leighton, Peter W. Shor
1997 J jnl
Random Debaters and the Hardness of Approximating Stochastic Functions.
SIAM J. Comput.
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor
1997 J jnl
Tight Bounds for the Maximum Acyclic Subgraph Problem.
J. Algorithms
Bonnie Berger, Peter W. Shor
1996 A* conf
Fault-Tolerant Quantum Computation.
FOCS
Peter W. Shor
1995 — conf
A Game-Theoretic Classification of Interactive Complexity Classes.
SCT
Joan Feigenbaum, Daphne Koller, Peter W. Shor
1995 J jnl
A New Proof of Cayley's Formula for Counting Labeled Trees.
J. Comb. Theory A
Peter W. Shor
1995 J jnl
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.
Chic. J. Theor. Comput. Sci.
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor
1994 A* conf
Algorithms for Quantum Computation: Discrete Logarithms and Factoring
FOCS
Peter W. Shor
1994 J jnl
Cube-Tilings of R
Discret. Comput. Geom.
J. C. Lagarias, Peter W. Shor
1994 J jnl
Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry.
J. Comput. Syst. Sci.
Bonnie Berger, John Rompel, Peter W. Shor
1994 — conf
Polynominal time algorithms for discrete logarithms and factoring on a quantum computer.
ANTS
Peter W. Shor
1994 — conf
Random Debaters and the Hardness of Approximating Stochastic Functions.
SCT
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor
1993 A* conf
Markov chains, computer proofs, and average-case analysis of best fit bin packing.
STOC
Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber
1993 J jnl
Packings in Two Dimensions: Asymptotic Average-Case Analysis of Algorithms.
Algorithmica
Edward G. Coffman Jr., Peter W. Shor
1993 A* conf
Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions.
STOC
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor
1993 J jnl
Three results on interactive communication.
IEEE Trans. Inf. Theory
Moni Naor, Alon Orlitsky, Peter W. Shor
1992 J jnl
Detecting and Decomposing Self-overlapping Curves.
Comput. Geom.
Peter W. Shor, Christopher J. Van Wyk
1992 J jnl
Finding Stabbing Lines in 3-Space.
Discret. Comput. Geom.
Marco Pellegrini, Peter W. Shor
1992 J jnl
Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands.
Oper. Res.
Julien Bramel, Edward G. Coffman Jr., Peter W. Shor, David Simchi-Levi
1992 J jnl
Steiner Tree Problems.
Algorithmica
Warren D. Smith, Peter W. Shor
1992 J jnl
The Rectilinear Steiner Arborescence Problem.
Algorithmica
Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor
1991 J jnl
A Simple Proof of the
SIAM J. Discret. Math.
Edward G. Coffman Jr., Peter W. Shor
1991 J jnl
Chip-firing Games on Graphs.
Eur. J. Comb.
Anders Björner, László Lovász, Peter W. Shor
1991 A* conf
Finding Stabbing Lines in 3-Dimensional Space.
SODA
Marco Pellegrini, Peter W. Shor
1991 A* conf
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
STOC
Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
1991 A* conf
How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing
FOCS
Peter W. Shor
1991 — conf
Implementation of a Combinatorial Multicommodity Flow Algorithm.
Network Flows And Matching
Tishya Leong, Peter W. Shor, Clifford Stein
1991 J jnl
Multilayer Grid Embeddings for VLSI.
Algorithmica
Alok Aggarwal, Maria M. Klawe, Peter W. Shor
1990 A* conf
Approximation Algorithms for the Maximum Acyclic Subgraph Problem.
SODA
Bonnie Berger, Peter W. Shor
1990 J jnl
Generalized Planar Matching.
J. Algorithms
Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder
1990 — conf
Stretchability of Pseudolines is NP-Hard.
Applied Geometry And Discrete Mathematics
Peter W. Shor
1989 J jnl
A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon.
Discret. Comput. Geom.
Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, Peter W. Shor
1989 J jnl
Application of Random Sampling in Computational Geometry, II.
Discret. Comput. Geom.
Kenneth L. Clarkson, Peter W. Shor
1989 B conf
Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version).
WADS
Alok Aggarwal, Shlomo Moran, Peter W. Shor, Subhash Suri
1989 — conf
Detecting and Decomposing Self-Overlapping Curves.
SCG
Peter W. Shor, Christopher J. Van Wyk
1989 A* conf
Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry
FOCS
Bonnie Berger, John Rompel, Peter W. Shor
1989 J jnl
Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.
J. Comb. Theory A
Pankaj K. Agarwal, Micha Sharir, Peter W. Shor
1989 J jnl
Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms.
Comb.
Tom Leighton, Peter W. Shor
1988 — conf
Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental.
SCG
Kenneth L. Clarkson, Peter W. Shor
1987 A* conf
A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon
STOC
Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, Peter W. Shor
1987 J jnl
A lower bound for 0, 1, * tournament codes.
Discret. Math.
Karen L. Collins, Peter W. Shor, John R. Stembridge
1987 J jnl
Geometric Applications of a Matrix-Searching Algorithm.
Algorithmica
Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, Robert E. Wilber
1986 — conf
Geometric Applications of a Matrix Searching Algorithm.
SCG
Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, Robert E. Wilber
1986 A* conf
Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms
STOC
Frank Thomson Leighton, Peter W. Shor
1986 J jnl
the average-case analysis of some on-line algorithms for bin packing.
Comb.
Peter W. Shor
1985 J jnl
A Counterexample to the Triangle Conjecture.
J. Comb. Theory A
Peter W. Shor
1984 A* conf
On the Pagenumber of Planar Graphs
STOC
Jonathan F. Buss, Peter W. Shor
1984 J jnl
Regressions and monotone chains: a ramsey - type extermal problem for partial orders.
Comb.
Douglas B. West, William T. Trotter, G. W. Peck, Peter W. Shor
1984 A* conf
The Average-Case Analysis of Some On-Line Algorithms for Bin Packing
FOCS
Peter W. Shor
1982 J jnl
A Lower Bound for the Length of a Partial Transversal in a Latin Square.
J. Comb. Theory A
Peter W. Shor