Ronald de Wolf

SIGACT News, 2007

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.

[BibT_eX]

[DOI]

Hartmut Klauck

Robert Spalek

SIAM J. Comput., 2007

Robust Polynomials and Quantum Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Exponential separations for one-way quantum communication complexity, with applications to cryptography.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

On Computation and Communication with Small Bias.

[BibT_eX]

[DOI]

Nikolai K. Vereshchagin

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.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Julia Kempe

Electron. Colloquium Comput. Complex., 2006

Lower Bounds on Matrix Rigidity Via a Quantum Argument.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Strengths and Weaknesses of Quantum Fingerprinting.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Julia Kempe

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Quantum Algorithms for Element Distinctness.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval.

[BibT_eX]

[DOI]

Stephanie Wehner

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.

[BibT_eX]

[DOI]

Iordanis Kerenidis

J. Comput. Syst. Sci., 2004

Quantum symmetrically-private information retrieval.

[BibT_eX]

[DOI]

Iordanis Kerenidis

Inf. Process. Lett., 2004

Quantum Communication Cannot Simulate a Public Coin

[BibT_eX]

[DOI]

Dmitry Gavinsky

Julia Kempe

CoRR, 2004

Algorithmic Clustering of Music Based on String Compression.

[BibT_eX]

[DOI]

Rudi Cilibrasi

Paul M. B. Vitányi

Comput. Music. J., 2004

Algorithmic Clustering of Music.

[BibT_eX]

[DOI]

Rudi Cilibrasi

Paul M. B. Vitányi

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

2003

Nondeterministic Quantum Query and Communication Complexities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Book reviews: On "An Introduction to Quantum Computing Algorithms" by A. O. Pittenger, "Quantum Computing" by M. Hirvensalo, and "Classical and Quantum Computation" by A. Yu. Kitaev, A. Shen, and M. N. Vyalyi.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2003

Quantum zero-error algorithms cannot be composed.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

Robust Quantum Algorithms and Polynomials

[BibT_eX]

[DOI]

CoRR, 2003

Quantum Search on Bounded-Error Inputs.

[BibT_eX]

[DOI]

Peter Høyer

Michele Mosca

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Quantum communication and complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Complexity measures and decision tree complexity: a survey.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Exponential Lower Bound for 2-Query Locally Decodable Codes

[BibT_eX]

[DOI]

Iordanis Kerenidis

Electron. Colloquium Comput. Complex., 2002

Improved Quantum Communication Complexity Bounds for Disjointness and Equality.

[BibT_eX]

[DOI]

Peter Høyer

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

On Quantum Versions of the Yao Principle.

[BibT_eX]

[DOI]

Mart de Graaf

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001

Marked PCP is decidable.

[BibT_eX]

[DOI]

Vesa Halava

Mika Hirvensalo

Theor. Comput. Sci., 2001

Quantum lower bounds by polynomials.

[BibT_eX]

[DOI]

J. ACM, 2001

Communication Complexity Lower Bounds by Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Nondeterministic Quantum Query and Quantum Communication Complexities

[BibT_eX]

[DOI]

CoRR, 2000

Average-Case Quantum Query Complexity.

[BibT_eX]

[DOI]

Andris Ambainis

Proceedings of the STACS 2000, 2000

Private Quantum Channels.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

A Lower Bound for Quantum Search of an Ordered List.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Decidability and Undecidability of Marked PCP.

[BibT_eX]

[DOI]

Vesa Halava

Mika Hirvensalo

Proceedings of the STACS 99, 1999

Bounds for Small-Error and Zero-Error Quantum Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Lower Bounds for Quantum Search and Derandomization

[BibT_eX]

[DOI]

CoRR, 1998

1997

Foundations of Inductive Logic Programming

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 1228, Springer, ISBN: 3-540-62927-0, 1997

1996

Least Generalizations and Greatest Specializations of Sets of Clauses.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 1996

Least Generalizations under Implication.

[BibT_eX]

[DOI]

Proceedings of the Inductive Logic Programming, 6th International Workshop, 1996

A Complete Method for Program Specialization Based on Unfolding.

[BibT_eX]

Proceedings of the 12th European Conference on Artificial Intelligence, 1996

1995

The Equivalence of the Subsumption Theorem and the Refutation-Completeness for Unconstrained Resolution.

[BibT_eX]

[DOI]