Ronald de Wolf

According to our database1, Ronald de Wolf authored at least 86 papers between 1995 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving.
CoRR, 2019

Quantum Computing: Lecture Notes.
CoRR, 2019

Two New Results About Quantum Exact Learning.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Optimal Quantum Sample Complexity of Learning Algorithms.
J. Mach. Learn. Res., 2018

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Improved bounds on Fourier entropy and Min-entropy.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Two new results about quantum exact learning.
CoRR, 2018

Convex optimization using quantum oracles.
CoRR, 2018

2017
Guest Column: A Survey of Quantum Learning Theory.
SIGACT News, 2017

Optimizing the number of gates in quantum search.
Quantum Information & Computation, 2017

Some upper and lower bounds on PSD-rank.
Math. Program., 2017

Attacks on the AJPS Mersenne-based cryptosystem.
IACR Cryptology ePrint Archive, 2017

The potential impact of quantum computers on society.
Ethics Inf. Technol., 2017

A Survey of Quantum Learning Theory.
CoRR, 2017

Optimal Parallel Quantum Query Algorithms.
Algorithmica, 2017

Quantum SDP-Solvers: Better Upper and Lower Bounds.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
A Survey of Quantum Property Testing.
Theory of Computing, Graduate Surveys, 2016

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Sum-of-Squares Degree of Symmetric Quadratic Functions.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Rational approximations and quantum algorithms with postselection.
Quantum Information & Computation, 2015

Exponential Lower Bounds for Polytopes in Combinatorial Optimization.
J. ACM, 2015

Query Complexity in Expectation.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
Computational Complexity, 2014

2013
Error-Correcting Data Structures.
SIAM J. Comput., 2013

The non-adaptive query complexity of testing k-parities.
Chicago J. Theor. Comput. Sci., 2013

Fooling One-Sided Quantum Protocols.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Optimal quantum query bounds for almost all Boolean functions.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
Near-Optimal and Explicit Bell Inequality Violations.
Theory of Computing, 2012

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

New bounds on the classical and quantum communication complexity of some graph properties.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011
Quantum Proofs for Classical Theorems.
Theory of Computing, Graduate Surveys, 2011

Uniform approximation by (quantum) polynomials.
Quantum Information & Computation, 2011

Bell Inequalities: What Do We Know about Them and Why Should Cryptographers Care? - (Invited Talk).
Proceedings of the Information Theoretic Security - 5th International Conference, 2011

2010
Upper bounds on the noise threshold for fault-tolerant quantum computing.
Quantum Information & Computation, 2010

New Results on Quantum Property Testing.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.
Proceedings of the Approximation, 2010

2009
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.
SIAM J. Comput., 2009

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation.
Electronic Colloquium on Computational Complexity (ECCC), 2009

A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs.
Algorithmica, 2009

Error-Correcting Data Structures.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Locally Decodable Quantum Codes.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008
A Brief Introduction to Fourier Analysis on the Boolean Cube.
Theory of Computing, Graduate Surveys, 2008

Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography.
SIAM J. Comput., 2008

A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions.
Quantum Information & Computation, 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.
Chicago J. Theor. Comput. Sci., 2008

A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
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, 2007

Robust Polynomials and Quantum Algorithms.
Theory Comput. Syst., 2007

Exponential separations for one-way quantum communication complexity, with applications to cryptography.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

On Computation and Communication with Small Bias.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Lower Bounds on Matrix Rigidity Via a Quantum Argument.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Strengths and Weaknesses of Quantum Fingerprinting.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
Quantum Algorithms for Element Distinctness.
SIAM J. Comput., 2005

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Exponential lower bound for 2-query locally decodable codes via a quantum argument.
J. Comput. Syst. Sci., 2004

Quantum symmetrically-private information retrieval.
Inf. Process. Lett., 2004

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Electronic Colloquium on Computational Complexity (ECCC), 2004

Quantum Communication Cannot Simulate a Public Coin
CoRR, 2004

Algorithmic Clustering of Music Based on String Compression.
Computer Music Journal, 2004

Algorithmic Clustering of Music.
Proceedings of the 4th International Conference on WEB Delivering of Music (WEDELMUSIC 2004), 2004

2003
Nondeterministic Quantum Query and Communication Complexities.
SIAM J. Comput., 2003

Book review.
Quantum Information & Computation, 2003

Quantum zero-error algorithms cannot be composed.
Inf. Process. Lett., 2003

Robust Quantum Algorithms and Polynomials
CoRR, 2003

Quantum Search on Bounded-Error Inputs.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002
Quantum communication and complexity.
Theor. Comput. Sci., 2002

Complexity measures and decision tree complexity: a survey.
Theor. Comput. Sci., 2002

Exponential Lower Bound for 2-Query Locally Decodable Codes
Electronic Colloquium on Computational Complexity (ECCC), 2002

Improved Quantum Communication Complexity Bounds for Disjointness and Equality.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

On Quantum Versions of the Yao Principle.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001
Marked PCP is decidable.
Theor. Comput. Sci., 2001

Quantum lower bounds by polynomials.
J. ACM, 2001

Communication Complexity Lower Bounds by Polynomials.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Nondeterministic Quantum Query and Quantum Communication Complexities
CoRR, 2000

Average-Case Quantum Query Complexity.
Proceedings of the STACS 2000, 2000

Private Quantum Channels.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
A Lower Bound for Quantum Search of an Ordered List.
Inf. Process. Lett., 1999

Decidability and Undecidability of Marked PCP.
Proceedings of the STACS 99, 1999

Bounds for Small-Error and Zero-Error Quantum Algorithms.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Lower Bounds for Quantum Search and Derandomization
CoRR, 1998

1996
Least Generalizations and Greatest Specializations of Sets of Clauses.
J. Artif. Intell. Res., 1996

Least Generalizations under Implication.
Proceedings of the Inductive Logic Programming, 6th International Workshop, 1996

A Complete Method for Program Specialization Based on Unfolding.
Proceedings of the 12th European Conference on Artificial Intelligence, 1996

1995
The Equivalence of the Subsumption Theorem and the Refutation-Completeness for Unconstrained Resolution.
Proceedings of the Algorithms, 1995


  Loading...