Andris Ambainis

According to our database1, Andris Ambainis authored at least 159 papers between 1994 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Parity oblivious d-level random access codes and class of noncontextuality inequalities.
Quantum Information Processing, 2019

Quantum Lower Bounds for 2D-Grid and Dyck Language.
CoRR, 2019

Quadratic speedup for finding marked vertices by quantum walks.
CoRR, 2019

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Quantum security proofs using semi-classical oracles.
IACR Cryptology ePrint Archive, 2018

On Block Sensitivity and Fractional Block Sensitivity.
CoRR, 2018

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test.
Proceedings of the SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29, 2018

2017
Separations in Query Complexity Based on Pointer Functions.
J. ACM, 2017

All Classical Adversary Methods are Equivalent for Total Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Understanding Quantum Algorithms via Query Complexity.
CoRR, 2017

Optimal one-shot quantum algorithm for EQUALITY and AND.
CoRR, 2017

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Exact Quantum Query Complexity of \text EXACT_k, l^n.
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

2016
Quantum Algorithm for Search on Grids.
Encyclopedia of Algorithms, 2016

Quantum Algorithm for Element Distinctness.
Encyclopedia of Algorithms, 2016

Superlinear Advantage for Exact Quantum Algorithms.
SIAM J. Comput., 2016

Rūsiņš Mārtiņš Freivalds (1942-2016).
Bulletin of the EATCS, 2016

Exact quantum query complexity of EXACTk, ln.
CoRR, 2016

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

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

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

Sensitivity Versus Certificate Complexity of Boolean Functions.
Proceedings of the Computer Science - Theory and Applications, 2016

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions.
Proceedings of the 31st Conference on Computational Complexity, 2016

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.
Proceedings of the 31st Conference on Computational Complexity, 2016

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

Correcting for potential barriers in quantum walk search.
Quantum Information & Computation, 2015

Spatial search on grids with minimum memory.
Quantum Information & Computation, 2015

Exact quantum algorithms have advantage for almost all Boolean functions.
Quantum Information & Computation, 2015

Almost quadratic gap between partition complexity and query/communication complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Automata and Quantum Computing.
CoRR, 2015

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

Almost quadratic gap between partition complexity and query/communication complexity.
CoRR, 2015

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014
The Need for Structure in Quantum Speedups.
Theory of Computing, 2014

Quantum algorithms for search with wildcards and combinatorial group testing.
Quantum Information & Computation, 2014

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding.
IACR Cryptology ePrint Archive, 2014

Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma.
Electronic Colloquium on Computational Complexity (ECCC), 2014

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Fast Matrix Multiplication: Limitations of the Laser Method.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Tighter Relations Between Sensitivity and Other Complexity Measures.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Exact query complexity of some special classes of Boolean functions.
CoRR, 2014

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

Recent Developments in Quantum Algorithms and Complexity.
Proceedings of the Descriptional Complexity of Formal Systems, 2014

On Physical Problems that are Slightly More Difficult than QMA.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
On symmetric nonlocal games.
Theor. Comput. Sci., 2013

Weak Parity.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Parameterized Quantum Query Complexity of Graph Collision
CoRR, 2013

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

Exact Quantum Query Complexity of EXACT and THRESHOLD.
Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games.
Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

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

Worst Case Analysis of Non-local Games.
Proceedings of the SOFSEM 2013: Theory and Practice of Computer Science, 2013

2012
A quantum lovász local lemma.
J. ACM, 2012

Superiority of exact quantum automata for promise problems.
Inf. Process. Lett., 2012

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification.
Proceedings of the Theory of Quantum Computation, 2012

Variable time amplitude amplification and quantum algorithms for linear algebra problems.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Advantage of Quantum Strategies in Random Symmetric XOR Games.
Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Grover's Algorithm with Errors.
Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Quantum Strategies Are Better Than Classical in Almost Any XOR Game.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
New separation between s(f) and bs(f).
Electronic Colloquium on Computational Complexity (ECCC), 2011

Quantum strategies are better than classical in almost any XOR game
CoRR, 2011

New separation between $s(f)$ and $bs(f)$
CoRR, 2011

Quantum Finite Automata.
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.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Quantum algorithms for formula evaluation.
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.
Theory of Computing, 2010

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

The quantum query complexity of certification.
Quantum Information & Computation, 2010

Limits on entropic uncertainty relations.
Quantum Information & Computation, 2010

Quantum Search with Variable Times.
Theory Comput. Syst., 2010

Symmetry-assisted adversaries for quantum state generation.
Electronic Colloquium on Computational Complexity (ECCC), 2010

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

Quantum algorithms for formula evaluation
CoRR, 2010

Nonlocal Quantum XOR Games for Large Number of Players.
Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

New Developments in Quantum Algorithms.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
Improved constructions of quantum automata.
Theor. Comput. Sci., 2009

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

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

2008
Quantum Algorithm for Search on Grids.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Quantum Algorithm for Element Distinctness.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Probabilistic and team PFIN-type learning: General properties.
J. Comput. Syst. Sci., 2008

Quantum Walks with Multiple or Moving Marked Locations.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Quantum Random Walks - New Method for Designing Quantum Algorithms.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Quantum Query Complexity of Boolean Functions with Small On-Sets.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007
Improved algorithms for quantum identification of Boolean oracles.
Theor. Comput. Sci., 2007

Quantum Walk Algorithm for Element Distinctness.
SIAM J. Comput., 2007

Quantum t-designs: t-wise independence in the quantum world.
Electronic Colloquium on Computational Complexity (ECCC), 2007

2006
The minimum distance problem for two-way entanglement purification.
IEEE Trans. Information Theory, 2006

Algebraic Results on Quantum Automata.
Theory Comput. Syst., 2006

Polynomial degree vs. quantum query complexity.
J. Comput. Syst. Sci., 2006

Computing with highly mixed states.
J. ACM, 2006

Quantum Algorithms for Matching and Network Flows.
Proceedings of the STACS 2006, 2006

Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.
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.
Theory of Computing, 2005

Quantum Search of Spatial Regions.
Theory of Computing, 2005

Coins make quantum walks faster.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Quantum search algorithms.
SIGACT News, 2004

Distributed construction of quantum fingerprints.
Quantum Information & Computation, 2004

Parsimony hierarchies for inductive inference.
J. Symb. Log., 2004

A new protocol and lower bounds for quantum coin flipping.
J. Comput. Syst. Sci., 2004

Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna
Electronic Colloquium on Computational Complexity (ECCC), 2004

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

Quantum algorithms a decade after shor.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Quantum Identification of Boolean Oracles.
Proceedings of the STACS 2004, 2004

Multiparty Quantum Coin Flipping.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption.
Proceedings of the Approximation, 2004

2003
Exact results for accepting probabilities of quantum automata.
Theor. Comput. Sci., 2003

The Quantum Communication Complexity of Sampling.
SIAM J. Comput., 2003

Cryptographic Randomized Response Techniques.
IACR Cryptology ePrint Archive, 2003

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information
Electronic Colloquium on Computational Complexity (ECCC), 2003

Size of Quantum Versus Deterministic Finite Automata.
Proceedings of the International Conference on VLSI, 2003

2002
Two-way finite automata with quantum and classical state.
Theor. Comput. Sci., 2002

ROM-based computation: quantum versus classical.
Quantum Information & Computation, 2002

Quantum Lower Bounds by Quantum Arguments.
J. Comput. Syst. Sci., 2002

Dense quantum coding and quantum finite automata.
J. ACM, 2002

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

Extracting Quantum Entanglement.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Hierarchies of probabilistic and team FIN-learning.
Theor. Comput. Sci., 2001

Probabilistic inductive inference: a survey.
Theor. Comput. Sci., 2001

The Communication Complexity of Enumeration, Elimination, and Selection.
J. Comput. Syst. Sci., 2001

On learning formulas in the limit and with assurance.
Inf. Process. Lett., 2001

Quantum walks on graphs.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

One-dimensional quantum walks.
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.
Proceedings of the STACS 2001, 2001

Quantum query algorithms and lower bounds.
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.
Inf. Process. Lett., 2000

Computing with highly mixed states (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

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

Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

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

1999
Ordinal Mind Change Complexity of Language Identification.
Theor. Comput. Sci., 1999

A Note on Quantum Black-Box Complexity of Almost all Boolean Functions.
Inf. Process. Lett., 1999

Inductive Inference with Procrastination: Back to Definitions.
Fundam. Inform., 1999

Bounded Depth Arithmetic Circuits: Counting and Closure
Electronic Colloquium on Computational Complexity (ECCC), 1999

Probabilistic Inductive Inference:a Survey
CoRR, 1999

Two-way finite automata with quantum and classical states
CoRR, 1999

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Quantum Finite Multitape Automata.
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.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Better Lower Bound for Quantum Algorithms Searching an Ordered List.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Probabilities to Accept Languages by Quantum Finite Automata.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
On Counting AC0 Circuits with Negative Constants
Electronic Colloquium on Computational Complexity (ECCC), 1998

1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Weak and Strong Recognition by 2-way Randomized Automata.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Nearly Tight Bounds on the Learnability of Evolution.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Team Learning as a Game.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

Effects of Kolmogorov Complexity Present in Inductive Inference as Well.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
Upper bound on the communication complexity of private information retrieval.
IACR Cryptology ePrint Archive, 1996

Communication Complexity in a 3-Computer Model.
Algorithmica, 1996

General Inductive Inference Types Based on Linearly-Ordered Sets.
Proceedings of the STACS 96, 1996

Upper Bounds on Multiparty Communication Complexity of Shifts.
Proceedings of the STACS 96, 1996

The Complexity of Probabilistic versus Deterministic Finite Automata.
Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Transformations that Preserve Learnability.
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995
Optimization Problem in Inductive Inference.
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.
Proceedings of the Computational Learning Theory, Second European Conference, 1995

Application of Kolmogorov Complexity to Inductive Inference with Limited Memory.
Proceedings of the Algorithmic Learning Theory, 6th International Conference, 1995

1994
Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference.
Proceedings of the Algorithmic Learning Theory, 1994


  Loading...