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

I recently received funding for a postdoc and a PhD student in quantum computing (specifically: quantum algorithms, communication complexity, applications to other areas). If you're good and you're interested: send me an e-mail. I'm looking for people whose primary focus and track-record is in computer science aspects, not physics.

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. Before that I was a PhD student at CWI and ILLC, and 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 student: Giannicola Scarpa (now a postdoc at Universitat Autonoma de Barcelona)
- Current PhD student: Srinivasan Arunachalam
- 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, ITCS 14, QIP 14, Complexity 14. - I am the PC chair of QIP 2015.
- I am part of an NWO-funded TOP-project about the intersection of approximation algorithms quantum information and semidefinite optimization, with Monique Laurent, Nikhil Bansal, Harry Buhrman.
- EU projects that I have been a part of: QAIP project, RESQ project, QAP project, QCS project, QALGO project.
- Some things that I am (co-)organizing or otherwise am part of:

the CWI Scientific Meeting, Algorithms and complexity seminar, CWI ondernemingsraad (OR), CWI Project Advisory Board, 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 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), 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.

To appear in ESA 14. Longer version at arxiv/1309.6116 - U. Mahadev and R. de Wolf.
Rational approximations and quantum algorithms with postselection.

to appear in*Quantum Information and Computation*, 2014. arxiv/1401.0912

- 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

- 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

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.

arXiv/1407.4308.

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

arXiv:1310.2035

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

- 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

- 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

Last update of this page: August 23, 2014 rdewolf at cwidotnl