[picture taken from this NRC interview, copyright Olivier Middendorp]

Address CWI Visiting address: Science Park 123, 1098 XG Amsterdam Postal address: P.O. Box 94079, 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

We have funding for a PhD student and a postdoc in quantum computing (specifically: quantum algorithms and complexity, incl. quantum communication and learning theory).

Foreign students: I don't supervise undergrad summer internships unless they are exceptionally well in tune with my research, so please don't send me your generic internship applications.

I am a researcher at the Algorithms and Complexity group of CWI (Dutch Centre for Mathematics and Computer Science) and part-time full professor at the ILLC of the University of Amsterdam. I'm also a member of QuSoft. A long time ago I was a PhD student at CWI and ILLC, and then a postdoc at UC Berkeley. My main scientific interests are quantum computing and complexity theory.

- My CV.
- My publications (see also DBLP, arxiv, and Google Scholar)
- Courses that I have taught or otherwise have been involved in.
- Former PhD students: Giannicola Scarpa (now a postdoc at Universidad Complutense de Madrid), Srinivasan Arunachalam (now a postdoc at MIT)
- Current PhD students: András Gilyén, and (co-supervised with Monique Laurent) Sander Gribling, and Joran van Apeldoorn
- I am a managing editor of Theory of Computing (an open-access journal) and an editor of SIAM Journal on Computing and of Quantum.
- 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, ITCS 14, QIP 14, Complexity 14, QIP 15 (PC chair), STOC 16, AQIS 16, STACS 17, PQCrypto 17, QIP 18, ICALP 18, NMC 19, TQC 19, ITCS 20, NMC 20, CCC 20. - I am part of an NWO-funded TOP-project about the intersection of approximation algorithms, quantum information, and semidefinite optimization, with Monique Laurent and Nikhil Bansal.
- EU projects that I have been a part of: QAIP project, RESQ project, QAP project, QCS project, QALGO project, QuantAlgo project.
- Some things that I am (co-)organizing or otherwise am part of:

TCS Amsterdam, the informatics advisory board of the Lorentz Center in Leiden, the Board of Examiners of the ILLC. - My TCS+ talk Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Fragment from Proust's "A la recherche du temps perdu" on art, life, and death.

- 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.

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

- R. de Wolf. Quantum Computing: Lecture Notes. Still evolving.

- 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 10), 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), pp.179-184. arxiv/1206.0717

Journal version in Computational Complexity, 23(2):305-322, 2014 (special issue on CCC 13). - 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 - S. Jeffery, F. Magniez, and R. de Wolf.
Optimal parallel quantum query algorithms.

In Proceedings of 22nd European Symposium on Algorithms (ESA 14), pp.592-604.

Journal version in*Algorithmica*, 79(2):509-529, 2017. arxiv/1309.6116 - U. Mahadev and R. de Wolf.
Rational approximations and quantum algorithms with postselection.

In*Quantum Information and Computation*, 15(3&4):295-307, 2014. arxiv/1401.0912 - J. Kaniewski, T. Lee, and R. de Wolf.
Query complexity in expectation.

In 42nd International Colloquium on Automata, Languages and Programming (ICALP 15), LNCS 9134, pp.761-772. arXiv/1411.7280. - A. Ambainis, A. Belovs, O. Regev, and R. de Wolf.
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.

In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 16), pp.903-922.

Also accepted for a talk at QIP 16. Full version at arXiv/1507.03126 - S. Arunachalam and R. de Wolf.
Optimizing the Number of Gates in Quantum Search.

In*Quantum Information and Computation*, 17(3&4), 2017. arXiv/1512.07550 - S. Arunachalam and R. de Wolf.
Optimal Quantum Sample Complexity of Learning Algorithms.

In Conference on Computational Complexity (CCC 17). Also accepted for a talk at QIP 17. arXiv/1607.00932

Journal version in*JMLR*, 19(71):1-36, 2018. - J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf.
Quantum SDP-Solvers: Better upper and lower bounds.

In 58th IEEE Symposium on Foundations of Computer Science (FOCS 17), pp.403-414. Much longer version at arXiv:1705.01843 - J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf. Convex optimization using quantum oracles. Accepted for a talk at QIP 19. arXiv:1809.00643
- S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf.
Two new results about quantum exact learning.

In 46th International Colloquium on Automata, Languages and Programming (ICALP 19), Leibniz International Proceedings in Informatics (LIPIcs) volume 132, pp.16:1-16:15. arXiv:1810.00481

- 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 (this partly supersedes quant-ph/0411051) - 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 12), 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 - M. Sinha and R. de Wolf.
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank.

Accepted for FOCS'19. arXiv:1811.10090 and ECCC

- 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.

- 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

Journal version*Exponential Lower Bounds for Polytopes in Combinatorial Optimization*in*Journal of the ACM*, 62(2):17, 2015.

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.

In Chicago Journal of Theoretical Computer Science, article 6, 2013. arXiv/1209.3849. - T. Lee, Z. Wei, and R. de Wolf.
Some upper and lower bounds on PSD-rank.

In*Mathematical Programming, Series A*, 162(1-2):495-521, 2017. View-only version at the journal. arXiv/1407.4308. Journal link - T. Lee, A. Prakash, H. Yuen, and R. de Wolf.
On the sum-of-squares degree of symmetric quadratic functions.

In Conference on Computational Complexity (CCC 16), paper 17, pp.1-31. arXiv/1601.02311 - K. de Boer, L. Ducas, S. Jeffery, and R. de Wolf.
Attacks on the AJPS Mersenne-based cryptosystem.

In Proceedings of PQCrypto 18, pp.101-120, 2018. Cryptology ePrint Archive: Report 2017/1171 - S. Arunachalam, S. Chakraborty, M. Koucky, N. Saurabh, and R. de Wolf. Improved bounds on Fourier entropy and Min-entropy. ECCC and arXiv:1809.09819

- R. de Wolf.
Quantum
Computation and Shor's Factoring Algorithm.

A short introduction, unpublished, 1999. - R. de Wolf.
Quantum
Communication and Complexity.

In*Theoretical Computer Science*, 287(1): 337-353, 2002. - 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.
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. - A. Montanaro and R. de Wolf.
A survey of quantum property testing.

In Theory of Computing (ToC Library, Graduate Surveys 7), 2016. arXiv:1310.2035 - S. Arunachalam and R. de Wolf.
A Survey of Quantum Learning Theory.

Computational Complexity Column,*ACM SIGACT News*, 48(2):41-67, June 2017. arXiv/1701.06806 fixes a few small glitches in the SIGACT version

- 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).

- 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.

- R. de Wolf. The potential impact of quantum computers on society. In
*Ethics and Information Technology*, 19(4):271-276, 2017. arXiv/1712.05380 - 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.

- 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
- Combinatorics with computer science applications, Amsterdam, Spring 2014
- Quantum computing, Amsterdam, Spring 2015
- Discrete Mathematics, at AUC (Amsterdam University College), Fall 2015. With Monique Laurent and Guido Schaeffer
- Combinatorics with computer science applications, Amsterdam, Spring 2016
- Quantum computing, Amsterdam, Spring 2017 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Spring 2018 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Spring 2019 (both a Master of Logic and a Mastermath course)

Last update of this page: July 10, 2019 rdewolf at cwidotnl