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

(Pronounced as "duh Wolf", with a short `o' as in `on';

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

I do not have any open PhD or postdoc positions at the moment.

Foreign students: I don't supervise summer internships unless they are by graduate students exceptionally well in tune with my research (which is theoretical computer science with focus on quantum algorithms and complexity; it's not physics, not cryptography, not data science, not web-design etc.), 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 and part of the Amsterdam TCS ecosystem. 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, though I have also dabbled in error-correcting codes, data structures, operations research, and theoretical machine learning.

- My CV.
- My publications (see also Google Scholar, arxiv, DBLP, MathSciNet).
- Courses that I have taught or otherwise have been involved in.
- Current PhD students: Yanlin Chen, Lynn Engelberts.
- Former PhD students: Giannicola Scarpa (graduated 2013, now an Associate Professor at Universidad Politécnica de Madrid), Srinivasan Arunachalam (graduated 2018, first a postdoc at MIT, now working at IBM Research), András Gilyén (graduated 2019, then a postdoc at Caltech, now at Rényi Institute of Mathematics, Budapest), Sander Gribling (graduated 2019, now a postdoc at IRIF, Paris, soon to be Assistant Professor at Tilburg University; supervised together with Monique Laurent), Jouke Witteveen (graduated 2020; supervised together with Leen Torenvliet), Joran van Apeldoorn (graduated 2020, then a postdoc at University of Amsterdam; supervised together with Monique Laurent).
- I am a coordinating editor of Quantum. I have been an editor of SIAM Journal on Computing, Theory of Computing, and 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, 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, FSTTCS 20, NMC 21, STOC 22, SODA 23, QIP 23, FOCS 23. - I am one of the PIs in the NWO Gravitation program Quantum Software Consortium.
- 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 recently was (co-)organizing or otherwise was part of:

TCS Amsterdam, the informatics advisory board of the Lorentz Center in Leiden, the Board of Examiners of the ILLC. - Some of my talks are online:

Exponential lower bounds for polytopes in combinatorial optimization, Hypercontractivity in theoretical computer science, Quantum SDP-solvers: Better upper and lower bounds, Quantum algorithms, The potential impact of quantum computers on society, Quantum coupon collector, Improved quantum boosting, Quantum algorithms for optimization, Quantum machine learning from a theoretical perspective. - 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. Quantum Computing: Lecture Notes. Still evolving, updated about once a year. Also at arXiv:1907.09415

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

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

Journal version in*Quantum*4, 230, 2020. Also arXiv:1705.01843 - J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf.
Convex optimization using quantum oracles.

In*Quantum*4, 220, 2020. Also presented as 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, 2019.

Journal version in*Quantum*5, 587, 2021. arXiv:1810.00481 - S. Apers and R. de Wolf.
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving.

In 61st IEEE Symposium on Foundations of Computer Science (FOCS 20).

Journal version in*SIAM Journal on Computing*, 51(6), 2022. Full version at arXiv:1911.07306 - S. Arunachalam, A. Belovs, A. Childs, R. Kothari, A. Rosmanis, and R. de Wolf.
Quantum Coupon Collector.

In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 20), Leibniz International Proceedings in Informatics (LIPIcs) volume 158, pp.10:1-10:17, 2020. arXiv:2002.07688 - A. Izdebski and R. de Wolf.
Improved Quantum Boosting.

In 31st European Symposium on Algorithms (ESA 23), Leibniz International Proceedings in Informatics (LIPIcs) volume 274, pp.64:1-64:16, 2023. arXiv:2009.08360 - N. Linden and R. de Wolf.
Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit.

In*Quantum*5, 436, 2021. arXiv:2009.08840 - J. van Apeldoorn, S. Gribling, Y. Li, H. Nieuwboer, M. Walter, and R. de Wolf.
Quantum algorithms for matrix scaling and matrix balancing.

In 48th International Colloquium on Automata, Languages and Programming (ICALP 21), Leibniz International Proceedings in Informatics (LIPIcs) volume 198, pp.110:1-17, 2021. arXiv:2011.12823 - N. Linden and R. de Wolf.
Average-case verification of the quantum Fourier transform enables worst-case phase estimation.

In*Quantum*6, 872, 2022. arXiv:2109.10215 - Y. Chen and R. de Wolf.
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints.

In 50th International Colloquium on Automata, Languages and Programming (ICALP 23), Leibniz International Proceedings in Informatics (LIPIcs) volume 261, pp.38:1-38:21, 2023.

Also presented as a talk at QIP'22. arXiv:2110.13086 - A. Cornelissen, N. Mande, M. Ozols, and R. de Wolf.
Exact quantum query complexity of computing Hamming weight modulo powers of two and three.

arXiv:2112.14682 - N. Bansal, M. Sinha, and R. de Wolf.
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms.

In 37th Computational Complexity Conference (CCC 2022), Leibniz International Proceedings in Informatics (LIPIcs) volume 234, 28:1-28:21, 2022. Accepted for a talk at QIP 23. arXiv:2203.00212 - N. Mande and R. de Wolf.
Tight Bounds for Quantum Phase Estimation and Related Problems.

In 31st European Symposium on Algorithms (ESA 23), Leibniz International Proceedings in Informatics (LIPIcs) volume 274, pp.81:1-81:16, 2023. arXiv:2305.04908

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

In 60th IEEE Symposium on Foundations of Computer Science (FOCS 19), pp.966-981. arXiv:1811.10090 and ECCC - S. Chakraborty, A. Chattopadhyay, P. Høyer, N. Mande, M. Paraashar, and R. de Wolf.
Symmetry and Quantum Query-To-Communication Simulation.

In Proceedings of STACS'22, Leibniz International Proceedings in Informatics (LIPIcs) volume 219, pp.20:1-20:19, 2022. arXiv:2012.05233 - O. Lalonde, N. Mande, and R. de Wolf.
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error.

To appear in FSTTCS 23. arXiv:2107.11806 and ECCC - S. Bravyi, Y. Sharma, M. Szegedy, and R. de Wolf.
Generating k EPR-Pairs from an n-Party Resource State.

Accepted for a talk at QIP 23. arXiv:2211.06497

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

This paper was awarded the 2022 STOC 10-year Test-of-Time Award and the 2023 Gödel Prize.

Popular article about this work by Alex van den Brandhof (in Dutch) - H. Buhrman, D. García-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.

In Proceedings of STACS'20, Leibniz International Proceedings in Informatics (LIPIcs) volume 154, pp.45:1-45:19, 2020.

Journal version in*ACM Transactions on Computation Theory*, Vol 13, Issue 4, 22:1-22:40 2021. ECCC and arXiv:1809.09819 - Y. Dulek, S. Jeffery, C. Majenz, C. Schaffner, F. Speelman, and R. de Wolf. A guide for new program committee members at theoretical computer science conferences. arXiv:2105.02773
- R. de Wolf.
Avi Wigderson's work and influence.

In*Nieuw Archief voor Wiskunde*, 5/23:31-34, 2022.

- 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)
- Quantum computing, Amsterdam, Spring 2020 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Spring 2021 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Spring 2022 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Spring 2023 (both a Master of Logic and a Mastermath course)
- Quantum computing, Amsterdam, Fall 2023 (both a Master of Logic and a Mastermath course)

Last update of this page: Oct 19, 2023 rdewolf at cwidotnl