2024
The Learning Stabilizers with Noise problem.
IACR Cryptol. ePrint Arch., 2024
A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension k Codes.
CoRR, 2024
2023
Bounding the Forward Classical Capacity of Bipartite Quantum Channels.
IEEE Trans. Inf. Theory, May, 2023
2021
Upper bound on the classical capacity of a quantum channel assisted by classical feedback.
Proceedings of the IEEE International Symposium on Information Theory, 2021
2019
Superadditivity in Trade-Off Capacities of Quantum Channels.
IEEE Trans. Inf. Theory, 2019
Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel.
IEEE Trans. Inf. Theory, 2019
Entropy Bound for the Classical Capacity of a Quantum Channel Assisted by Classical Feedback.
Proceedings of the IEEE International Symposium on Information Theory, 2019
2017
Superadditivity of the classical capacity with limited entanglement assistance.
CoRR, 2017
Quantum and Super-quantum enhancements to two-sender, two-receiver channels.
CoRR, 2017
2016
The Systematic Normal Form of Lattices.
CoRR, 2016
2015
New Constructions of Codes for Asymmetric Channels via Concatenation.
IEEE Trans. Inf. Theory, 2015
Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH.
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.
IEEE Trans. Inf. Theory, 2014
A new relativistic orthogonal states quantum key distribution protocol.
Quantum Inf. Comput., 2014
2012
Quantum money from knots.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012
2011
Quantum Interactive Proofs with Short Messages.
Theory Comput., 2011
High Performance Single-Error-Correcting Quantum Codes for Amplitude Damping.
IEEE Trans. Inf. Theory, 2011
Unstructured randomness, small gaps and localization.
Quantum Inf. Comput., 2011
Quantum adiabatic algorithms, small gaps, and different paths.
Quantum Inf. Comput., 2011
A complete resolution of the Keller maximum clique problem.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
2010
Time reversal and exchange symmetries of unitary gate capacities.
IEEE Trans. Inf. Theory, 2010
Questions answered. in theory.: http://cstheory.stackexchange.com/.
SIGACT News, 2010
C_3, semi-Clifford and genralized semi-Clifford operations.
Quantum Inf. Comput., 2010
Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol.
Proceedings of the Innovations in Computer Science, 2010
2009
Quantum Reverse Shannon Theorem.
CoRR, 2009
Generalized concatenation for quantum codes.
Proceedings of the IEEE International Symposium on Information Theory, 2009
2008
Channel-Adapted Quantum Error Correction for the Amplitude Damping Channel.
IEEE Trans. Inf. Theory, 2008
Estimating Jones polynomials is a complete problem for one clean qubit.
Quantum Inf. Comput., 2008
Entanglement purification with two-way classical communication.
Quantum Inf. Comput., 2008
Random Quantum Codes from Gaussian Ensembles and an Uncertainty Relation.
Open Syst. Inf. Dyn., 2008
A lower bound for the length of a partial transversal in a Latin square.
J. Comb. Theory A, 2008
The Power of Unentanglement.
Electron. Colloquium Comput. Complex., 2008
2006
On the Sum-of-Squares algorithm for bin packing.
J. ACM, 2006
2005
Remote preparation of quantum states.
IEEE Trans. Inf. Theory, 2005
2004
Progress in Quantum Algorithms.
Quantum Inf. Process., 2004
The classical capacity achievable by a quantum channel assisted by a limited entanglement.
Quantum Inf. Comput., 2004
The adaptive classical capacity of a quantum channel, or Information capacities of three symmetric pure states in three dimensions.
IBM J. Res. Dev., 2004
2003
Capacities of quantum channels and how to find them.
Math. Program., 2003
Why haven't more quantum algorithms been found?.
J. ACM, 2003
The Cutting-Stock Approach to Bin Packing: Theory and Experiments.
Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003
2002
Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem.
IEEE Trans. Inf. Theory, 2002
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Rev., 2002
2000
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discret. Math., 2000
Local rule mechanism for selecting icosahedral shell geometry.
Discret. Appl. Math., 2000
1999
Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems.
Math. Oper. Res., 1999
On the Structure of the Scaffolding Core of Bacteriophage T4.
J. Comput. Biol., 1999
A Self Organizing Bin Packing Heuristic.
Proceedings of the Algorithm Engineering and Experimentation, 1999
1998
Quantum Error Correction Via Codes Over GF(4).
IEEE Trans. Inf. Theory, 1998
Quantum Information Theory.
IEEE Trans. Inf. Theory, 1998
1997
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
SIAM J. Comput., 1997
Random Debaters and the Hardness of Approximating Stochastic Functions.
SIAM J. Comput., 1997
Bin packing with discrete item sizes, part II: Tight bounds on First Fit.
Random Struct. Algorithms, 1997
Tight Bounds for the Maximum Acyclic Subgraph Problem.
J. Algorithms, 1997
1996
Fault-Tolerant Quantum Computation.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
A New Proof of Cayley's Formula for Counting Labeled Trees.
J. Comb. Theory A, 1995
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.
Chic. J. Theor. Comput. Sci., 1995
A Game-Theoretic Classification of Interactive Complexity Classes.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995
1994
Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry.
J. Comput. Syst. Sci., 1994
Cube-Tilings of R<sup>n</sup> and Nonlinear Codes.
Discret. Comput. Geom., 1994
Algorithms for Quantum Computation: Discrete Logarithms and Factoring
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
Polynominal time algorithms for discrete logarithms and factoring on a quantum computer.
Proceedings of the Algorithmic Number Theory, First International Symposium, 1994
1993
Three results on interactive communication.
IEEE Trans. Inf. Theory, 1993
Packings in Two Dimensions: Asymptotic Average-Case Analysis of Algorithms.
Algorithmica, 1993
Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions.
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.
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.
Oper. Res., 1992
Finding Stabbing Lines in 3-Space.
Discret. Comput. Geom., 1992
Detecting and Decomposing Self-overlapping Curves.
Comput. Geom., 1992
The Rectilinear Steiner Arborescence Problem.
Algorithmica, 1992
1991
A Simple Proof of the <i>O</i>(sqrt(n log<sup>3/4</sup> <i>n</i>) Upright Matching Bound.
SIAM J. Discret. Math., 1991
Chip-firing Games on Graphs.
Eur. J. Comb., 1991
Multilayer Grid Embeddings for VLSI.
Algorithmica, 1991
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
Finding Stabbing Lines in 3-Dimensional Space.
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
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
Implementation of a Combinatorial Multicommodity Flow Algorithm.
Proceedings of the Network Flows And Matching, 1991
1990
Generalized Planar Matching.
J. Algorithms, 1990
Approximation Algorithms for the Maximum Acyclic Subgraph Problem.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990
Stretchability of Pseudolines is NP-Hard.
Proceedings of the Applied Geometry And Discrete Mathematics, 1990
1989
Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.
J. Comb. Theory A, 1989
Application of Random Sampling in Computational Geometry, II.
Discret. Comput. Geom., 1989
A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon.
Discret. Comput. Geom., 1989
Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms.
Comb., 1989
Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version).
Proceedings of the Algorithms and Data Structures, 1989
1988
Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988
1987
A lower bound for 0, 1, * tournament codes.
Discret. Math., 1987
Geometric Applications of a Matrix-Searching Algorithm.
Algorithmica, 1987
1986
the average-case analysis of some on-line algorithms for bin packing.
Comb., 1986
Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986
1985
A Counterexample to the Triangle Conjecture.
J. Comb. Theory A, 1985
1984
Regressions and monotone chains: a ramsey - type extermal problem for partial orders.
Comb., 1984
On the Pagenumber of Planar Graphs
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.
J. Comb. Theory A, 1982