Ronald de Wolf

Victor Chen, Elena Grigorescu, Ronald de Wolf: Error-Correcting Data Structures. SIAM J. Comput. 42(1): 84-111 (2013)

Hartmut Klauck, Ronald de Wolf: Fooling One-Sided Quantum Protocols. STACS 2013: 424-433

Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf: Optimal quantum query bounds for almost all Boolean functions. STACS 2013: 446-453

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. Theory of Computing 8(1): 623-645 (2012)

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf: New bounds on the classical and quantum communication complexity of some graph properties. FSTTCS 2012: 148-159

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. STOC 2012: 95-106

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf: New bounds on the classical and quantum communication complexity of some graph properties. CoRR abs/1204.4596 (2012)

Hartmut Klauck, Ronald de Wolf: Fooling One-Sided Quantum Protocols. CoRR abs/1204.4619 (2012)

Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf: The non-adaptive query complexity of testing k-parities. CoRR abs/1209.3849 (2012)

Andrew Drucker, Ronald de Wolf: Uniform approximation by (quantum) polynomials. Quantum Information & Computation 11(3&4): 215-225 (2011)

Andrew Drucker, Ronald de Wolf: Quantum Proofs for Classical Theorems. Theory of Computing, Graduate Surveys 2: 1-54 (2011)

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. IEEE Conference on Computational Complexity 2011: 157-166

Ronald de Wolf: Bell Inequalities: What Do We Know about Them and Why Should Cryptographers Care? - (Invited Talk). ICITS 2011: 117-119

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf: Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. CoRR abs/1111.0837 (2011)

Ronald de Wolf: A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Information & Computation 8(10): 943-950 (2010)

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Information & Computation 10(5&6): 361-376 (2010)

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf: Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM 2010: 476-489

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Ronald de Wolf: New Results on Quantum Property Testing. FSTTCS 2010: 145-156

Victor Chen, Elena Grigorescu, Ronald de Wolf: Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. STACS 2010: 203-214

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Ronald de Wolf: New Results on Quantum Property Testing. CoRR abs/1005.0523 (2010)

Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422-461 (2009)

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39(1): 1-24 (2009)

Jop Briët, Ronald de Wolf: Locally Decodable Quantum Codes. STACS 2009: 219-230

Ronald de Wolf: Error-Correcting Data Structures. STACS 2009: 313-324

Victor Chen, Elena Grigorescu, Ronald de Wolf: Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. CoRR abs/0909.3696 (2009)

Andrew Drucker, Ronald de Wolf: Quantum Proofs for Classical Theorems. CoRR abs/0910.3376 (2009)

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf: Better Gap-Hamming Lower Bounds via Better Round Elimination. CoRR abs/0912.5276 (2009)

Victor Chen, Elena Grigorescu, Ronald de Wolf: Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. Electronic Colloquium on Computational Complexity (ECCC) 16: 79 (2009)

Andrew Drucker, Ronald de Wolf: Quantum Proofs for Classical Theorems. Electronic Colloquium on Computational Complexity (ECCC) 16: 102 (2009)

Dmitry Gavinsky, Oded Regev, Ronald de Wolf: Simultaneous Communication Protocols with Quantum and Classical Messages. Chicago J. Theor. Comput. Sci. 2008 (2008)

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38(5): 1695-1708 (2008)

Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Theory of Computing, Graduate Surveys 1: 1-20 (2008)

Avraham Ben-Aroya, Oded Regev, Ronald de Wolf: A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. FOCS 2008: 477-486

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. ICALP (1) 2008: 845-856

Ronald de Wolf: Error-Correcting Data Structures. CoRR abs/0802.1471 (2008)

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM J. Comput. 36(5): 1472-1493 (2007)

Ronald de Wolf: Joint review of "An Introduction to Quantum Computing Algorithms by Arthur O. Pittenger, " Birkhäuser, ISBN: 0817641270; Quantum Computing by Mika Hirvensalo, " Springer, ISBN: 3540667830; and "Classical and Quantum Computation by A. Yu. Kitaev, A. Shen, and M. N. Vyalyi, " American Mathematical Society, ISBN: 082182161X. SIGACT News 38(1): 14-17 (2007)

Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC 2007: 516-525

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Strengths and Weaknesses of Quantum Fingerprinting. IEEE Conference on Computational Complexity 2006: 288-298

Ronald de Wolf: Lower Bounds on Matrix Rigidity Via a Quantum Argument. ICALP (1) 2006: 62-71

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. STOC 2006: 594-603

Andris Ambainis, Robert Spalek, Ronald de Wolf: A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. STOC 2006: 618-633

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Strengths and Weaknesses of Quantum Fingerprinting. CoRR abs/quant-ph/0603173 (2006)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. CoRR abs/quant-ph/0607174 (2006)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. Electronic Colloquium on Computational Complexity (ECCC) 13(086) (2006)

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. SIAM J. Comput. 34(6): 1324-1330 (2005)

Stephanie Wehner, Ronald de Wolf: Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. ICALP 2005: 1424-1436

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604

Ronald de Wolf: Lower Bounds on Matrix Rigidity via a Quantum Argument. CoRR abs/quant-ph/0505188 (2005)

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. CoRR abs/quant-ph/0511013 (2005)

Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. CoRR abs/quant-ph/0511200 (2005)

Iordanis Kerenidis, Ronald de Wolf: Quantum symmetrically-private information retrieval. Inf. Process. Lett. 90(3): 109-114 (2004)

Iordanis Kerenidis, Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69(3): 395-420 (2004)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. FOCS 2004: 12-21

Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Algorithmic Clustering of Music. WEDELMUSIC 2004: 110-117

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. CoRR quant-ph/0402123 (2004)

Stephanie Wehner, Ronald de Wolf: Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. CoRR quant-ph/0403140 (2004)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Quantum Communication Cannot Simulate a Public Coin. CoRR quant-ph/0411051 (2004)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. Electronic Colloquium on Computational Complexity (ECCC)(045) (2004)

Harry Buhrman, Ronald de Wolf: Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. 87(2): 79-84 (2003)

Ronald de Wolf: Book review. Quantum Information & Computation 3(1): 93-96 (2003)

Ronald de Wolf: Nondeterministic Quantum Query and Communication Complexities. SIAM J. Comput. 32(3): 681-699 (2003)

Peter Høyer, Michele Mosca, Ronald de Wolf: Quantum Search on Bounded-Error Inputs. ICALP 2003: 291-299

Iordanis Kerenidis, Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. STOC 2003: 106-115

Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Algorithmic Clustering of Music. CoRR cs.SD/0303025 (2003)

Peter Høyer, Michele Mosca, Ronald de Wolf: Quantum Search on Bounded-Error Inputs. CoRR quant-ph/0304052 (2003)

Iordanis Kerenidis, Ronald de Wolf: Quantum Symmetrically-Private Information Retrieval. CoRR quant-ph/0307076 (2003)

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Quantum Algorithms and Polynomials. CoRR quant-ph/0309220 (2003)

Ronald de Wolf: Quantum communication and complexity. Theor. Comput. Sci. 287(1): 337-353 (2002)

Harry Buhrman, Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1): 21-43 (2002)

Peter Høyer, Ronald de Wolf: Improved Quantum Communication Complexity Bounds for Disjointness and Equality. STACS 2002: 299-310

Mart de Graaf, Ronald de Wolf: On Quantum Versions of the Yao Principle. STACS 2002: 347-358

Iordanis Kerenidis, Ronald de Wolf: Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument. CoRR quant-ph/0208062 (2002)

Harry Buhrman, Ronald de Wolf: Quantum Zero-Error Algorithms Cannot be Composed. CoRR quant-ph/0211029 (2002)

Iordanis Kerenidis, Ronald de Wolf: Exponential Lower Bound for 2-Query Locally Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC)(059) (2002)

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM 48(4): 778-797 (2001)

Vesa Halava, Mika Hirvensalo, Ronald de Wolf: Marked PCP is decidable. Theor. Comput. Sci. 255(1-2): 193-204 (2001)

Harry Buhrman, Ronald de Wolf: Communication Complexity Lower Bounds by Polynomials. IEEE Conference on Computational Complexity 2001: 120-130

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. IEEE Conference on Computational Complexity 2001: 131-137

Peter Høyer, Ronald de Wolf: Improved Quantum Communication Complexity Bounds for Disjointness and Equality. CoRR quant-ph/0109068 (2001)

Mart de Graaf, Ronald de Wolf: On Quantum Versions of the Yao Principle. CoRR quant-ph/0109070 (2001)

Ronald de Wolf: Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. IEEE Conference on Computational Complexity 2000: 271-278

Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf: Private Quantum Channels. FOCS 2000: 547-553

Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity. STACS 2000: 133-144

Ronald de Wolf: Nondeterministic Quantum Query and Quantum Communication Complexities. CoRR cs.CC/0001014 (2000)

Harry Buhrman, Ronald de Wolf: A Lower Bound for Quantum Search of an Ordered List. Inf. Process. Lett. 70(5): 205-209 (1999)

Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka: Bounds for Small-Error and Zero-Error Quantum Algorithms. FOCS 1999: 358-368

Vesa Halava, Mika Hirvensalo, Ronald de Wolf: Decidability and Undecidability of Marked PCP. STACS 1999: 207-216

Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka: Bounds for Small-Error and Zero-Error Quantum Algorithms. CoRR cs.CC/9904019 (1999)

Harry Buhrman, Ronald de Wolf: Communication Complexity Lower Bounds by Polynomials. CoRR cs.CC/9910010 (1999)

Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity. CoRR quant-ph/9904079 (1999)

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum Lower Bounds by Polynomials. FOCS 1998: 352-361

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum Lower Bounds by Polynomials. CoRR quant-ph/9802049 (1998)

Harry Buhrman, Ronald de Wolf: Lower Bounds for Quantum Search and Derandomization. CoRR quant-ph/9811046 (1998)

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf (Eds.): Foundations of Inductive Logic Programming. Lecture Notes in Computer Science 1228, Springer 1997, isbn 3-540-62927-0

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf: Least Generalizations and Greatest Specializations of Sets of Clauses. J. Artif. Intell. Res. (JAIR) 4: 341-363 (1996)

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf: A Complete Method for Program Specialization Based on Unfolding. ECAI 1996: 438-442

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf: Least Generalizations under Implication. Inductive Logic Programming Workshop 1996: 285-298

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf: Least Generalizations and Greatest Specializations of Sets of Clauses. CoRR cs.AI/9605102 (1996)

Shan-Hwei Nienhuys-Cheng, Ronald de Wolf: The Equivalence of the Subsumption Theorem and the Refutation-Completeness for Unconstrained Resolution. ASIAN 1995: 269-285