Andris Ambainis

CoRR, 2017

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games.

[BibT_eX]

[DOI]

Martins Kokainis

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Exact Quantum Query Complexity of \text EXACT_k, l^n.

[BibT_eX]

[DOI]

Daniel Nagaj

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

2016

Quantum Algorithm for Search on Grids.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Quantum Algorithm for Element Distinctness.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Superlinear Advantage for Exact Quantum Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Rūsiņš Mārtiņš Freivalds (1942-2016).

[BibT_eX]

[DOI]

Bull. EATCS, 2016

Exact quantum query complexity of EXACTk, ln.

[BibT_eX]

[DOI]

Daniel Nagaj

CoRR, 2016

Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities.

[BibT_eX]

[DOI]

CoRR, 2016

Quantum Query Complexity of Almost All Functions with Fixed On-set Size.

[BibT_eX]

[DOI]

Comput. Complex., 2016

Optimal One-shot Quantum Algorithm for EQUALITY and AND.

[BibT_eX]

[DOI]

Balt. J. Mod. Comput., 2016

Four Collaborations with Rūsiņš Freivalds.

[BibT_eX]

[DOI]

Balt. J. Mod. Comput., 2016

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Sensitivity Versus Certificate Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Krisjanis Prusis

Jevgenijs Vihrovs

Proceedings of the Computer Science - Theory and Applications, 2016

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions.

[BibT_eX]

[DOI]

Martins Kokainis

Robin Kothari

Proceedings of the 31st Conference on Computational Complexity, 2016

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2015

Correcting for potential barriers in quantum walk search.

[BibT_eX]

[DOI]

Thomas G. Wong

Quantum Inf. Comput., 2015

Spatial search on grids with minimum memory.

[BibT_eX]

[DOI]

Renato Portugal

Nikolay Nahimov

Quantum Inf. Comput., 2015

Exact quantum algorithms have advantage for almost all Boolean functions.

[BibT_eX]

[DOI]

Jozef Gruska

Shenggen Zheng

Quantum Inf. Comput., 2015

Separations in Query Complexity Based on Pointer Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Almost quadratic gap between partition complexity and query/communication complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Automata and Quantum Computing.

[BibT_eX]

[DOI]

Abuzer Yakaryilmaz

CoRR, 2015

Optimal Classical Random Access Codes Using Single d-level Systems.

[BibT_eX]

[DOI]

Dmitry Kravchenko

Ashutosh Rai

CoRR, 2015

Almost quadratic gap between partition complexity and query/communication complexity.

[BibT_eX]

[DOI]

Martins Kokainis

CoRR, 2015

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.

[BibT_eX]

[DOI]

Yuval Filmus

François Le Gall

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Quantum algorithms for search with wildcards and combinatorial group testing.

[BibT_eX]

[DOI]

Ashley Montanaro

Quantum Inf. Comput., 2014

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding.

[BibT_eX]

[DOI]

Ansis Rosmanis

Dominique Unruh

IACR Cryptol. ePrint Arch., 2014

Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma.

[BibT_eX]

[DOI]

Jevgenijs Vihrovs

Electron. Colloquium Comput. Complex., 2014

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity.

[BibT_eX]

[DOI]

Krisjanis Prusis

Electron. Colloquium Comput. Complex., 2014

Fast Matrix Multiplication: Limitations of the Laser Method.

[BibT_eX]

[DOI]

Yuval Filmus

François Le Gall

Electron. Colloquium Comput. Complex., 2014

Tighter Relations Between Sensitivity and Other Complexity Measures.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Exact query complexity of some special classes of Boolean functions.

[BibT_eX]

[DOI]

Jozef Gruska

Shenggen Zheng

CoRR, 2014

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

[BibT_eX]

[DOI]

Ronald de Wolf

Comput. Complex., 2014

Recent Developments in Quantum Algorithms and Complexity.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2014

On Physical Problems that are Slightly More Difficult than QMA.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

On symmetric nonlocal games.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Weak Parity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Parameterized Quantum Query Complexity of Graph Collision

[BibT_eX]

[DOI]

CoRR, 2013

New upper bound on block sensitivity and certificate complexity in terms of sensitivity.

[BibT_eX]

[DOI]

CoRR, 2013

Exact Quantum Query Complexity of EXACT and THRESHOLD.

[BibT_eX]

[DOI]

Juris Smotrovs

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games.

[BibT_eX]

[DOI]

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Optimal quantum query bounds for almost all Boolean functions.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Worst Case Analysis of Non-local Games.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2013: Theory and Practice of Computer Science, 2013

2012

A quantum lovász local lemma.

[BibT_eX]

[DOI]

Julia Kempe

Or Sattath

J. ACM, 2012

Superiority of exact quantum automata for promise problems.

[BibT_eX]

[DOI]

Abuzer Yakaryilmaz

Inf. Process. Lett., 2012

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification.

[BibT_eX]

[DOI]

Proceedings of the Theory of Quantum Computation, 2012

Variable time amplitude amplification and quantum algorithms for linear algebra problems.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Advantage of Quantum Strategies in Random Symmetric XOR Games.

[BibT_eX]

[DOI]

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Grover's Algorithm with Errors.

[BibT_eX]

[DOI]

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Quantum Strategies Are Better Than Classical in Almost Any XOR Game.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

New separation between s(f) and bs(f).

[BibT_eX]

[DOI]

Xiaoming Sun

Electron. Colloquium Comput. Complex., 2011

Quantum strategies are better than classical in almost any XOR game

[BibT_eX]

[DOI]

CoRR, 2011

New separation between $s(f)$ and $bs(f)$

[BibT_eX]

[DOI]

Xiaoming Sun

CoRR, 2011

Quantum Finite Automata.

[BibT_eX]

Proceedings of the Third Workshop on Non-Classical Models for Automata and Applications - NCMA 2011, Milan, Italy, July 18, 2011

Quantum Property Testing for Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Andrew M. Childs

Yi-Kai Liu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Quantum algorithms for formula evaluation.

[BibT_eX]

[DOI]

Proceedings of the Quantum Cryptography and Computing, 2010

A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search.

[BibT_eX]

[DOI]

Theory Comput., 2010

Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1) on a Quantum Computer.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

The quantum query complexity of certification.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2010

Limits on entropic uncertainty relations.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2010

Quantum Search with Variable Times.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Symmetry-assisted adversaries for quantum state generation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

[BibT_eX]

[DOI]

CoRR, 2010

Quantum algorithms for formula evaluation

[BibT_eX]

[DOI]

CoRR, 2010

Nonlocal Quantum XOR Games for Large Number of Players.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

New Developments in Quantum Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

Improved constructions of quantum automata.

[BibT_eX]

[DOI]

Nikolajs Nahimovs

Theor. Comput. Sci., 2009

The Need for Structure in Quantum Speedups.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2009

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

[BibT_eX]

[DOI]

CoRR, 2009

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

[BibT_eX]

[DOI]

Robert Spalek

Ronald de Wolf

Algorithmica, 2009

2008

Quantum Algorithm for Search on Grids.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Quantum Algorithm for Element Distinctness.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Probabilistic and team PFIN-type learning: General properties.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Quantum Walks with Multiple or Moving Marked Locations.

[BibT_eX]

[DOI]

Alexander Rivosh

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Quantum Random Walks - New Method for Designing Quantum Algorithms.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Quantum Query Complexity of Boolean Functions with Small On-Sets.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

Improved algorithms for quantum identification of Boolean oracles.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Quantum Walk Algorithm for Element Distinctness.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Quantum t-designs: t-wise independence in the quantum world.

[BibT_eX]

[DOI]

Joseph Emerson

Electron. Colloquium Comput. Complex., 2007

2006

The minimum distance problem for two-way entanglement purification.

[BibT_eX]

[DOI]

Daniel Gottesman

IEEE Trans. Inf. Theory, 2006

Algebraic Results on Quantum Automata.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Polynomial degree vs. quantum query complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Computing with highly mixed states.

[BibT_eX]

[DOI]

Leonard J. Schulman

Umesh V. Vazirani

J. ACM, 2006

Quantum Algorithms for Matching and Network Flows.

[BibT_eX]

[DOI]

Robert Spalek

Proceedings of the STACS 2006, 2006

Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range.

[BibT_eX]

[DOI]

Theory Comput., 2005

Quantum Search of Spatial Regions.

[BibT_eX]

[DOI]

Scott Aaronson

Theory Comput., 2005

Coins make quantum walks faster.

[BibT_eX]

[DOI]

Julia Kempe

Alexander Rivosh

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Quantum search algorithms.

[BibT_eX]

[DOI]

SIGACT News, 2004

Distributed construction of quantum fingerprints.

[BibT_eX]

[DOI]

Yaoyun Shi

Quantum Inf. Comput., 2004

Parsimony hierarchies for inductive inference.

[BibT_eX]

[DOI]

J. Symb. Log., 2004

A new protocol and lower bounds for quantum coin flipping.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

[BibT_eX]

[DOI]

CoRR, 2004

Quantum algorithms a decade after shor.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Quantum Identification of Boolean Oracles.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.

[BibT_eX]

[DOI]

Ke Yang

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Multiparty Quantum Coin Flipping.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption.

[BibT_eX]

[DOI]

Adam D. Smith

Proceedings of the Approximation, 2004

2003

Exact results for accepting probabilities of quantum automata.

[BibT_eX]

[DOI]

Arnolds Kikusts

Theor. Comput. Sci., 2003

The Quantum Communication Complexity of Sampling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Cryptographic Randomized Response Techniques.

[BibT_eX]

[DOI]

Markus Jakobsson

Helger Lipmaa

IACR Cryptol. ePrint Arch., 2003

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

[BibT_eX]

[DOI]

Ke Yang

Electron. Colloquium Comput. Complex., 2003

Size of Quantum Versus Deterministic Finite Automata.

[BibT_eX]

Proceedings of the International Conference on VLSI, 2003

2002

Two-way finite automata with quantum and classical state.

[BibT_eX]

[DOI]

John Watrous

Theor. Comput. Sci., 2002

ROM-based computation: quantum versus classical.

[BibT_eX]

[DOI]

Benjamin C. Travaglione

Michael A. Nielsen

Howard M. Wiseman

Quantum Inf. Comput., 2002

Quantum Lower Bounds by Quantum Arguments.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Dense quantum coding and quantum finite automata.

[BibT_eX]

[DOI]

J. ACM, 2002

Delayed Binary Search, or Playing Twenty Questions with a Procrastinator.

[BibT_eX]

[DOI]

Stephen A. Bloch

David L. Schweizer

Algorithmica, 2002

Extracting Quantum Entanglement.

[BibT_eX]

[DOI]

Adam D. Smith

Ke Yang

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Hierarchies of probabilistic and team FIN-learning.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Probabilistic inductive inference: a survey.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

The Communication Complexity of Enumeration, Elimination, and Selection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

On learning formulas in the limit and with assurance.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2001

Quantum walks on graphs.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

One-dimensional quantum walks.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On the Class of Languages Recognizable by 1-Way Quantum Finite Automata.

[BibT_eX]

[DOI]

Arnolds Kikusts

Maris Valdats

Proceedings of the STACS 2001, 2001

Quantum query algorithms and lower bounds.

[BibT_eX]

[DOI]

Proceedings of the Classical and New Paradigms of Computation and their Complexity Hierarchies, 2001

2000

How rich is the structure of the intrinsic complexity of learning.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Computing with highly mixed states (extended abstract).

[BibT_eX]

[DOI]

Leonard J. Schulman

Umesh V. Vazirani

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Average-Case Quantum Query Complexity.

[BibT_eX]

[DOI]

Ronald de Wolf

Proceedings of the STACS 2000, 2000

Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function.

[BibT_eX]

[DOI]

Satyanarayana V. Lokam

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

Private Quantum Channels.

[BibT_eX]

[DOI]

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

1999

Ordinal Mind Change Complexity of Language Identification.

[BibT_eX]

[DOI]

Sanjay Jain

Arun Sharma

Theor. Comput. Sci., 1999

A Note on Quantum Black-Box Complexity of Almost all Boolean Functions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Inductive Inference with Procrastination: Back to Definitions.

[BibT_eX]

[DOI]

Carl H. Smith

Fundam. Informaticae, 1999

Bounded Depth Arithmetic Circuits: Counting and Closure

[BibT_eX]

[DOI]

Eric Allender

David A. Mix Barrington

Samir Datta

Huong LeThanh

Electron. Colloquium Comput. Complex., 1999

Probabilistic Inductive Inference:a Survey

[BibT_eX]

[DOI]

CoRR, 1999

Two-way finite automata with quantum and classical states

[BibT_eX]

[DOI]

John Watrous

CoRR, 1999

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Quantum Finite Multitape Automata.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM '99, Theory and Practice of Informatics, 26th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 27, 1999

Playing Twenty Questions with a Procrastinator.

[BibT_eX]

[DOI]

Stephen A. Bloch

David L. Schweizer

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Better Lower Bound for Quantum Algorithms Searching an Ordered List.

[BibT_eX]

[DOI]

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

Probabilities to Accept Languages by Quantum Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

On Counting AC0 Circuits with Negative Constants

[BibT_eX]

[DOI]

David A. Mix Barrington

Huong LeThanh

Electron. Colloquium Comput. Complex., 1998

1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Weak and Strong Recognition by 2-way Randomized Automata.

[BibT_eX]

[DOI]

Marek Karpinski

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Nearly Tight Bounds on the Learnability of Evolution.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Team Learning as a Game.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

Effects of Kolmogorov Complexity Present in Inductive Inference as Well.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996

Upper bound on the communication complexity of private information retrieval.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 1996

Communication Complexity in a 3-Computer Model.

[BibT_eX]

[DOI]

Algorithmica, 1996

General Inductive Inference Types Based on Linearly-Ordered Sets.

[BibT_eX]

[DOI]

Carl H. Smith

Proceedings of the STACS 96, 1996

Upper Bounds on Multiparty Communication Complexity of Shifts.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

The Complexity of Probabilistic versus Deterministic Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Transformations that Preserve Learnability.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995

Optimization Problem in Inductive Inference.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, 1995

The power of procrastination in inductive inference: How it depends on used ordinal notations.

[BibT_eX]

[DOI]

Proceedings of the Computational Learning Theory, Second European Conference, 1995

Application of Kolmogorov Complexity to Inductive Inference with Limited Memory.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 6th International Conference, 1995

1994

Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference.

[BibT_eX]

[DOI]