Ronald de Wolf

Address     CWI
            Visiting address: Science Park 123, NL-1098 XG Amsterdam
            Postal address: P.O. Box 94079, NL-1090 GB Amsterdam 
            The Netherlands
Office      L234 (2nd floor of the new wing of the CWI building)
Telephone   020-5924078 (+31 20 5924078)
E-mail      rdewolf at cwidotnl

• My CV.
• My publications (see also DBLP, arxiv, and Google Scholar)
  • PhD thesis
  • My inaugural lecture
  • Quantum computation
  • Quantum communication
  • Locally decodable codes, private information retrieval, error-correcting data structures
  • Other theoretical computer science
  • Survey papers
  • Inductive logic programming
  • Book reviews
  • Philosophy
• Courses that I have taught or otherwise have been involved in.
• PhD student: Giannicola Scarpa
• I am a managing editor of Theory of Computing (an open-access journal) and an editor of Quantum Information and Computation.
• Conferences where I was/am on the program or steering committee:
  QIP 01, QIP 07, QIP 08, Complexity 08, QIP 09, ICALP 09, QIP 10, SOFSEM 10, Complexity 10, STACS 11, MFCS 11, QIP 12, TQC 12, STOC 13, ESA 13, Complexity 14, ITCS 14.
• Some things that I am or have been (co-)organizing: the CWI Scientific Meeting, Algorithms and complexity seminar, CWI ondernemingsraad (OR), TCS Amsterdam.
• EU projects that I have been a part of: QAIP project, RESQ project, QAP project, QCS project, QALGO project.
• Fragment from Proust's "A la recherche du temps perdu" on art, life, and death.
• A beautiful place

Publications

My PhD thesis

• R. de Wolf. Quantum Computing and Communication Complexity, University of Amsterdam, 2001.
  It got me ERCIM's 2003 Cor Baayen Award.
  Send me an e-mail with your address if you would like to receive a bound copy.

My inaugural lecture

• R. de Wolf. What quantum computing can do for you, University of Amsterdam, September 20, 2012.

Quantum computation

• R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum Lower Bounds by Polynomials.
  In 39th IEEE Symposium on Foundations of Computer Science (FOCS 98), pp.352-361. quant-ph/9802049
  Journal version in Journal of the ACM, 48(4):778-797, 2001.
• H. Buhrman and R. de Wolf. A Lower Bound for Quantum Search of an Ordered List.
  In Information Processing Letters, 70(5):205-209, 1999.
• H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms.
  In 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), pp.358-368. cs.CC/9904019
• A. Ambainis and R. de Wolf. Average-Case Quantum Query Complexity.
  In 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS 00), LNCS 1770, pp.133-144. quant-ph/9904079
  Journal version in Journal of Physics A: Mathematical and General, Special Issue on Quantum Information and Computation, 34(35):6741-6754, 2001.
• R. de Wolf. Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity.
  In 15th IEEE Annual Conference on Computational Complexity (CCC 00), pp.271-278. cs.CC/0001014
  Journal version in SIAM Journal on Computing, 32(3):681-699, 2003.
• H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf. Quantum Algorithms for Element Distinctness.
  In 16th IEEE Annual Conference on Computational Complexity (CCC 01), pp.131-137. quant-ph/0007016
  Journal version in SIAM Journal on Computing, 34(6):1324-1330, 2005.
• M. de Graaf and R. de Wolf. On Quantum Versions of the Yao Principle.
  In 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 02), LNCS 2285, pp.347-358. quant-ph/0109070
• H. Buhrman and R. de Wolf. Quantum Zero-Error Algorithms Cannot be Composed.
  In Information Processing Letters, 87(2):79-84, 2003. quant-ph/0211029
• P. Høyer, M. Mosca, and R. de Wolf. Quantum Search on Bounded-Error Inputs.
  In 30th International Colloquium on Automata, Languages and Programming (ICALP 03), LNCS 2719, pp.291-299. quant-ph/0304052
• H. Klauck, R. Špalek, and R. de Wolf. Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
  In 45th IEEE Symposium on Foundations of Computer Science (FOCS 04), pp.12-21. quant-ph/0402123
  Journal version in SIAM Journal on Computing, 36(5):1472-1493, 2007.
• H. Buhrman, I. Newman, H. Röhrig, and R. de Wolf. Robust Quantum Algorithms and Polynomials.
  In 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 05), LNCS 3404, pp.593-604. quant-ph/0309220
  Journal version in Theory of Computing Systems, 40(4):379-395, 2007 (special issue on STACS 05).
• A. Ambainis, R. Špalek, and R. de Wolf. A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs.
  In 38th Annual ACM Symposium on Theory of Computing (STOC 06), pp.618-633. quant-ph/0511200
  Journal version in Algorithmica, 55(3):422-461, 2009.
• J. Kempe, O. Regev, F. Unger, and R. de Wolf. Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing.
  In 35th International Colloquium on Automata, Languages and Programming (ICALP 08), LNCS 5125(1), pp.845-856. quant-ph/0802.1464
  Journal version in Quantum Information and Computation, 10(5-6):361-376, 2010.
• R. de Wolf. A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions.
  In Quantum Information and Computation, 8(10):943-950, 2008. quant-ph/0802.1816
• S. Chakraborty, E. Fischer, A. Matsliah, and R. de Wolf. New Results on Quantum Property Testing.
  In 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), pp.145-156. arxiv/1005.0523
• A. Drucker and R. de Wolf. Uniform Approximation by (Quantum) Polynomials.
  In Quantum Information and Computation, 11(3&4):215-225, 2011. arxiv/1008.1599
• A. Ambainis and R. de Wolf. How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?.
  In 28th IEEE Annual Conference on Computational Complexity (CCC 13). arxiv/1206.0717
• A. Ambainis, A. Backurs, J. Smotrovs, and R. de Wolf. Optimal quantum query bounds for almost all Boolean functions.
  In 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS 13), pp.446-453. arxiv/1208.1122

Quantum communication

• H. Buhrman and R. de Wolf. Communication Complexity Lower Bounds by Polynomials.
  In 16th IEEE Annual Conference on Computational Complexity (CCC 01), pp.120-130. cs.CC/9910010
• A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf. Private Quantum Channels.
  In 41st IEEE Symposium on Foundations of Computer Science (FOCS 00), pp.547-553. quant-ph/0003101
• H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum Fingerprinting.
  In Physical Review Letters, 87(16), September 26, 2001. quant-ph/0102001
  References to this work in Physics News and Technology Research News.
  A more popular version for the NVTI Newsletter, 2002.
• P. Høyer and R. de Wolf. Improved Quantum Communication Complexity Bounds for Disjointness and Equality.
  In 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 02), LNCS 2285, pp.299-310. quant-ph/0109068
  Journal version of parts of this in SIAM Journal on Computing, 32(3):681-699, 2003.
• R. de Wolf. Lower Bounds on Matrix Rigidity via a Quantum Argument.
  In 33rd International Colloquium on Automata, Languages and Programming (ICALP 06), LNCS 4051, pp.62-71. quant-ph/0505188
• D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf. Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.
  In 38th Annual ACM Symposium on Theory of Computing (STOC 06), pp.594-603.
  Journal version in SIAM Journal on Computing, 39(1):1-39, 2009. Special issue on STOC 06. quant-ph/0511013
• D. Gavinsky, J. Kempe, and R. de Wolf. Strengths and Weaknesses of Quantum Fingerprinting.
  In 21st IEEE Annual Conference on Computational Complexity (CCC 06), pp.288-295. quant-ph/0603173
• D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography.
  In 39th Annual ACM Symposium on Theory of Computing (STOC 07), pp.516-525.
  Journal version in SIAM Journal on Computing, 38(5):1695-1708, 2008. quant-ph/0611209
• A. Ben-Aroya, O. Regev, and R. de Wolf. A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs.
  In 49th IEEE Symposium on Foundations of Computer Science (FOCS 08), pp.477-486. quant-ph/0705.3806
• D. Gavinsky, O. Regev, and R. de Wolf. Simultaneous Communication Protocols with Quantum and Classical Messages.
  In Chicago Journal of Theoretical Computer Science, article 7, 2008. quant-ph/0807.2758
• H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf. Near-Optimal and Explicit Bell Inequality Violations.
  In 26th IEEE Conference on Computational Complexity (CCC 11), pp.157-166. Also accepted to QIP'11 as a featured talk.
  Journal version in Theory of Computing, 8(27):623-645, 2012. arxiv/1012.5043 (this supersedes arxiv/1007.2359)
  
• G. Ivanyos, H. Klauck, T. Lee, M. Santha, and R. de Wolf. New bounds on the classical and quantum communication complexity of some graph properties.
  In 32nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), pp.148-159. arxiv/1204.4596
• H. Klauck and R. de Wolf. Fooling One-Sided Quantum Protocols.
  In 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS 13), pp.424-433. arxiv/1204.4619

Locally decodable codes, private information retrieval, error-correcting data structures

• I. Kerenidis and R. de Wolf. Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument.
  In 35th Annual ACM Symposium on Theory of Computing (STOC 03), pp.106-115. quant-ph/0208062
  Journal version in Journal of Computer and System Sciences, 69(3):395-420, 2004 (special issue on STOC 03).
• I. Kerenidis and R. de Wolf. Quantum Symmetrically-Private Information Retrieval.
  In Information Processing Letters, 90(3):109-114, 2004. quant-ph/0307076
• S. Wehner and R. de Wolf. Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval.
  In 32nd International Colloquium on Automata, Languages and Programming (ICALP 05), LNCS 3580, pp.1424-1436. quant-ph/0403140
• J. Briët and R. de Wolf. Locally Decodable Quantum Codes.
  In 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 09), pp.219-230. quant-ph/0806.2101
• R. de Wolf. Error-Correcting Data Structures.
  In 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 09), pp.313-324. cs.DS/0802.1471
• V. Chen, E. Grigorescu, and R. de Wolf. Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation.
  In 27th Annual Symposium on Theoretical Aspects of Computer Science (STACS 10), pp.203-214. Preprint at ECCC and arXiv/0909.3696.
  Journal version combining the previous two papers, in SIAM Journal on Computing, 42(1):84-111, 2013.

Other theoretical computer science

• V. Halava, M. Hirvensalo, and R. de Wolf. Decidability and Undecidability of Marked PCP.
  In 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS 99), LNCS 1563, pp.210-219.
  Also available as TUCS Technical Report No.201.
  Journal version in Theoretical Computer Science, 255:193-204, 2001.
• R. Cilibrasi, P. Vitányi, and R. de Wolf. Algorithmic Clustering of Music.
  In Proceedings of IEEE 4th International Conference on Web Delivery of Music (Wedelmusic 04), pp.110-117.
  Journal version (word file) in Computer Music Journal, 28:4, 49-67, 2004. Earlier version at cs.SD/0303025
  References to this work in New Scientist, Ars Technica, Technology Research News, NRC Handelsblad, Deutschlandfunk, Neural.it, ERCIM News, and Pour la science.
• H. Buhrman, N. Vereshchagin, and R. de Wolf. On Computation and Communication with Small Bias.
  In 22nd IEEE Annual Conference on Computational Complexity (CCC 07), pp.24-32.
• J. Brody, A. Chakrabarti, O. Regev, T. Vidick, and R. de Wolf. Better Gap-Hamming Lower Bounds via Better Round Elimination.
  In Proceedings of 13th RANDOM, 2010, pp.476-489. arXiv/0912.5276.
• S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds.
  In 44th Annual ACM Symposium on Theory of Computing (STOC 12), pp.95-106 (shared Best Paper Award). arxiv/1111.0837
  Popular article about this work by Alex van den Brandhof (in Dutch)
• H. Buhrman, D. Garcia-Soriano, A. Matsliah, and R. de Wolf. The non-adaptive query complexity of testing k-parities.
  Submitted. arXiv/1209.3849.

Survey papers

• R. de Wolf. Quantum Computation and Shor's Factoring Algorithm.
  A short introduction, unpublished, 1999.
• H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey.
  In Theoretical Computer Science, 288(1):21-43, 2002.
• R. de Wolf. Quantum Communication and Complexity.
  In Theoretical Computer Science, 287(1): 337-353, 2002.
• R. de Wolf. A Brief Introduction to Fourier Analysis on the Boolean Cube.
  In Theory of Computing (ToC Library, Graduate Surveys 1), 6, 2008. Don't try this at home...
• H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. Non-locality and Communication Complexity.
  Reformatted version in Reviews of Modern Physics, 82:665-698, 2010. quant-ph/0907.3584
• A. Drucker and R. de Wolf. Quantum proofs for classical theorems.
  In Theory of Computing (ToC Library, Graduate Surveys 2), 2011. Preprint (of earlier version) at quant-ph/0910.3376 and ECCC.

Inductive logic programming

• S.H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Programming, Lecture Notes in Artificial Intelligence 1228, Springer, May 1997 (amazon.com link). This is a very theoretical book on ILP. The first part gives a self-contained introduction to the theory of resolution-based theorem proving and logic programming, the second part in-depth covers most of the topics in ILP that we considered of foundational importance for the field. Writing this book took us about two and a half years of sweat and struggle, but I'm still quite happy with the final result (except for a serious error in the appendix to Chapter 18, which was pointed out to us by Chandra Reddy). Krzysztof Apt kindly wrote the foreword to our book, and also put it as review 97-6 on a page of positive reviews.
• Contributions to Inductive Logic Programming, my Master's thesis on computer science. It is superseded by the above book.
• S.H. Nienhuys-Cheng and R. de Wolf. Least Generalizations and Greatest Specializations of Sets of Clauses.
  Journal of Artificial Intelligence Research, 4:341-363, 1996.
• S.H. Nienhuys-Cheng and R. de Wolf. A Complete Method for Program Specialization Based on Unfolding.
  In 12th European Conference on Artificial Intelligence (ECAI 96), pp.438-442, Wiley.
  As I'm having some trouble compiling this file into pdf, you may download the LaTeX-source of the paper instead.
• S.H. Nienhuys-Cheng and R. de Wolf. Least Generalizations under Implication.
  In 6th Workshop on Inductive Logic Programming (ILP 96), LNAI 1314, pp.285-298, 1997.
• S.H. Nienhuys-Cheng and R. de Wolf. The Subsumption Theorem in Inductive Logic Programming: Facts and Fallacies.
  In L. De Raedt (ed.), Advances in Inductive Logic Programming, pp.265-276, IOS Press, 1996. (Early version in ILP 95.)
• S.H. Nienhuys-Cheng and R. de Wolf. The Equivalence of the Subsumption Theorem and the Refutation-Completeness for Unconstrained Resolution.
  In Asean Computer Science Conference (ACSC 95), LNCS 1023, pp.269-285.
• S.H. Nienhuys-Cheng and R. de Wolf. Tidying up the Mess Around the Subsumption Theorem in Inductive Logic Programming.
  In 7th Dutch Conference on AI (NAIC 95), pp.221-230, Erasmus University Rotterdam (Best Paper Award).

Book reviews

• R. de Wolf. Book review of: C.P. Williams and S.H. Clearwater, Explorations in Quantum Computing, Springer, 1998.
  In Science of Computer Programming, 32:213-216, 1998.
• R. de Wolf. Book review of three quantum books by Pittenger, Hirvensalo, and Kitaev-Shen-Vyalyi.
  In Quantum Information and Computation, 3(1):93-96, 2003.

Philosophy

• Philosophical applications of computational learning theory, my Master's thesis in philosophy. The first part gives a formal "proof" of Chomsky's ideas about the necessity of an innate universal grammar. The second part is about proofs of Occam's razor, which states that you should always select the simplest hypothesis consistent with given data. The thesis also contains a lot of historical and philosophical background concerning these two topics.

Courses I've taught

• Combinatorics for information sciences, Amsterdam, Fall 2006
• Combinatorics with computer science applications, Leiden, Spring 2008
• Quantum computing, Amsterdam, Spring 2011
• Combinatorics with computer science applications, Amsterdam, Spring 2012
• Quantum computing, Amsterdam, Spring 2013

Other courses I've been involved in

• Logic for computer scientists, Amsterdam, Fall 1997
• Logic for computer scientists, Amsterdam, Fall 1998
• Kolmogorov Complexiteit, Datacompressie en Leren, Amsterdam, Spring 2000
• Quantum computing, Amsterdam, Fall 2000
• Quantum computing, Amsterdam, Spring 2003