Richard Cleve

According to our database, Richard Cleve authored at least 43 papers between 1986 and 2025.

Collaborative distances:

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

2025

Linear gate bounds against natural functions for position-verification.

Vahid R. Asadi, Richard Cleve, Eric Culf, Alex May

Quantum, 2025

2022

Constant gap between conventional strategies and those based on C*-dynamics for self-embezzlement.

Richard Cleve, Benoit Collins, Li Liu, Vern I. Paulsen

Quantum, 2022

2017

Efficient Quantum Algorithms for Simulating Lindblad Evolution.

Richard Cleve, Chunhao Wang

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Near-linear constructions of exact unitary 2-designs.

Richard Cleve, Debbie W. Leung, Li Liu, Chunhao Wang

Quantum Inf. Comput., 2016

2014

Gate-efficient discrete simulations of continuous-time quantum query algorithms.

Dominic W. Berry, Richard Cleve, Sevag Gharibian

Quantum Inf. Comput., 2014

Computing with a full memory: catalytic space.

Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman

Proceedings of the Symposium on Theory of Computing, 2014

Exponential improvement in precision for simulating sparse Hamiltonians.

Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma

Proceedings of the Symposium on Theory of Computing, 2014

Characterization of Binary Constraint System Games.

Richard Cleve, Rajat Mittal

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2012

Reconstructing Strings from Substrings with Quantum Queries.

Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2009

Discrete-Query Quantum Algorithm for NAND Trees.

Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David L. Yonge-Mallo

Theory Comput., 2009

Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's.

Richard Cleve, Dmitry Gavinsky, Rahul Jain

Quantum Inf. Comput., 2009

Efficient discrete-time simulations of continuous-time quantum query algorithms.

Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando D. Somma, David L. Yonge-Mallo

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Quantum Algorithms for Evaluating Min-MaxTrees.

Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo

Proceedings of the Theory of Quantum Computation, 2008

2007

Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems.

Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Quantum lower bounds for the Goldreich-Levin problem.

Mark Adcock, Richard Cleve, Kazuo Iwama, Raymond H. Putra, Shigeru Yamashita

Inf. Process. Lett., 2006

New Limits on Fault-Tolerant Quantum Computation.

Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

Classical and quantum fingerprinting with shared randomness and one-sided error.

Rolf T. Horn, A. J. Scott, Jonathan Walgate, Richard Cleve, A. I. Lvovsky, Barry C. Sanders

Quantum Inf. Comput., 2005

2004

Consequences and Limits of Nonlocal Strategies.

Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Exponential algorithmic speedup by a quantum walk.

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Editorial.

Richard Cleve

Quantum Inf. Comput., 2002

Sharp Quantum versus Classical Query Complexity Separations.

J. Niel de Beaudrap, Richard Cleve, John Watrous

Algorithmica, 2002

A Quantum Goldreich-Levin Theorem with Cryptographic Applications.

Mark Adcock, Richard Cleve

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2000

Quantum Entanglement and Communication Complexity.

Harry Buhrman, Richard Cleve, Wim van Dam

SIAM J. Comput., 2000

Fast parallel circuits for the quantum Fourier transform.

Richard Cleve, John Watrous

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

The Query Complexity of Order-Finding.

Richard Cleve

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Bounds for Small-Error and Zero-Error Quantum Algorithms.

Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Interpolating Arithmetic Read-Once Formulas in Parallel.

Nader H. Bshouty, Richard Cleve

SIAM J. Comput., 1998

On quantum algorithms.

Richard Cleve, Artur Ekert, Leah Henderson, Chiara Macchiavello, Michele Mosca

Complex., 1998

Quantum vs. Classical Communication and Computation.

Harry Buhrman, Richard Cleve, Avi Wigderson

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Quantum Entanglement and the Communication Complexity of the Inner Product Function.

Richard Cleve, Wim van Dam, Michael Nielsen, Alain Tapp

Proceedings of the Quantum Computing and Quantum Communications, 1998

Quantum Lower Bounds by Polynomials.

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1995

Size-Depth Tradeoffs for Algebraic Formulas.

Nader H. Bshouty, Richard Cleve, Wayne Eberly

SIAM J. Comput., 1995

Oracles and Queries That Are Sufficient for Exact Learning

Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon

Electron. Colloquium Comput. Complex., 1995

1994

Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).

Nader H. Bshouty, Richard Cleve, Sampath Kannan, Christino Tamon

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

A Note on Constructive Lower Bounds for the Ramsey Numbers <i>R</i>(3, <i>t</i>).

Fan R. K. Chung, Richard Cleve, Paul Dagum

J. Comb. Theory B, 1993

1992

On the Exact Learning of Formulas in Parallel (Extended Abstract)

Nader H. Bshouty, Richard Cleve

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Size-Depth Tradeoffs for Algebraic Formulae

Nader H. Bshouty, Richard Cleve, Wayne Eberly

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

1990

Towards Optimal Simulations of Formulas by Bounded-Width Programs

Richard Cleve

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Complexity Theoretic Issues Concerning Block Ciphers Related to D.E.S.

Richard Cleve

Proceedings of the Advances in Cryptology, 1990

1989

Methodologies for designing block ciphers and cryptographic protocols.

Richard Cleve

PhD thesis, 1989

Controlled Gradual Disclosure Schemes for Random Bits and Their Applications.

Richard Cleve

Proceedings of the Advances in Cryptology, 1989

1988

Computing Algebraic Formulas Using a Constant Number of Registers

Michael Ben-Or, Richard Cleve

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1986

Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract)

Richard Cleve

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