Andris Ambainis

264 papers A* 32A 23B 19C 2Misc 2Journal 153Unranked 27

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A hierarchy of constant communication complexity. Inf. Comput. Andris Ambainis, Hartmut Klauck, Debbie Lim
2026	J	`jnl`	Quantum algorithm for apprenticeship learning. Quantum Mach. Intell. Andris Ambainis, Debbie Lim
2025	J	`jnl`	A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model. CoRR Andris Ambainis, João F. Doriguello, Debbie Lim
2025	J	`jnl`	A Hierarchy for Constant Communication Complexity. CoRR Andris Ambainis, Hartmut Klauck, Debbie Lim
2025	J	`jnl`	An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. Comput. Complex. Andris Ambainis, Aleksandrs Belovs
2025	J	`jnl`	Quantum Search on Bipartite Multigraphs. CoRR Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal
2025	J	`jnl`	Quantum computing and artificial intelligence: status and perspectives. CoRR Giovanni Acampora, Andris Ambainis, Natalia Ares, Leonardo Banchi, Pallavi Bhardwaj, Daniele Binosi, G. Andrew D. Briggs, Tommaso Calarco, Vedran Dunjko, Jens Eisert, Olivier Ezratty, Paul Erker, Federico Fedele, Elies Gil-Fuster, Martin Gärttner, Mats Granath, Markus Heyl, Iordanis Kerenidis, Matthias Klusch, Anton Frisk Kockum, Richard Kueng, Mario Krenn, Jörg Lässig, Antonio Macaluso, Sabrina Maniscalco, Florian Marquardt, Kristel Michielsen, Gorka Muñoz-Gil, Daniel Müssig, Hendrik Poulsen Nautrup, Evert P. L. van Nieuwenburg, Roman Orus, Jörg Schmiedmayer, Markus Schmitt, Philipp Slusallek, Filippo Vicentini, Christof Weitenberg, Frank K. Wilhelm
2024	J	`jnl`	Quantum Algorithm for the Domatic Number Problem. Balt. J. Mod. Comput. Andris Ambainis, Ilja Repko
2023	J	`jnl`	A hybrid quantum-classical approach for inference on restricted Boltzmann machines. CoRR Martins Kalis, Andris Locans, Rolands Sikovs, Hassan Naseri, Andris Ambainis
2023	J	`jnl`	A hybrid quantum-classical approach for inference on restricted Boltzmann machines. Quantum Mach. Intell. Martins Kalis, Andris Locans, Rolands Sikovs, Hassan Naseri, Andris Ambainis
2023	A	`conf`	An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC Andris Ambainis, Aleksandrs Belovs
2023	—	`conf`	Improved Algorithm and Lower Bound for Variable Time Quantum Search. TQC Andris Ambainis, Martins Kokainis, Jevgenijs Vihrovs
2023	B	`conf`	Quantum Complexity for Vector Domination Problem. SOFSEM Andris Ambainis, Ansis Zvirbulis
2023	J	`jnl`	Quantum bounds for 2D-grid and Dyck language. Quantum Inf. Process. Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
2022	J	`jnl`	Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
2021	—	`conf`	A Note About Claw Function with a Small Range. TQC Andris Ambainis, Kaspars Balodis, Janis Iraids
2021	J	`jnl`	A note about claw function with a small range. CoRR Andris Ambainis, Kaspars Balodis, Janis Iraids
2021	J	`jnl`	All Classical Adversary Methods Are Equivalent for Total Functions. ACM Trans. Comput. Theory Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, Aleksejs Zajakins
2021	—	`ch.`	Automata and quantum computing. Handbook of Automata Theory (II.) Andris Ambainis, Abuzer Yakaryilmaz
2021	J	`jnl`	On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung
2020	A*	`conf`	Quadratic speedup for finding marked vertices by quantum walks. STOC Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis
2020	—	`conf`	Quantum Algorithms for Computational Geometry Problems. TQC Andris Ambainis, Nikita Larka
2020	B	`conf`	Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. MFCS Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
2020	J	`jnl`	Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. CoRR Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
2020	J	`jnl`	Quantum algorithms for computational geometry problems. CoRR Andris Ambainis, Nikita Larka
2019	J	`jnl`	Parity oblivious Quantum Inf. Process. Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai
2019	J	`jnl`	Quadratic speedup for finding marked vertices by quantum walks. CoRR Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis
2019	J	`jnl`	Quantum Lower Bounds for 2D-Grid and Dyck Language. CoRR Andris Ambainis, Kaspars Balodis, Janis Iraids, Krisjanis Prusis, Juris Smotrovs
2019	—	`conf`	Quantum Security Proofs Using Semi-classical Oracles. CRYPTO (2) Andris Ambainis, Mike Hamburg, Dominique Unruh
2019	A*	`conf`	Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
2018	A	`conf`	All Classical Adversary Methods are Equivalent for Total Functions. STACS Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
2018	J	`jnl`	Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. Scott Aaronson, Andris Ambainis
2018	B	`conf`	Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test. SOFSEM Farid M. Ablayev, Andris Ambainis, Kamil Khadiev, Aliya Khadieva
2018	J	`jnl`	On Block Sensitivity and Fractional Block Sensitivity. CoRR Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
2018	J	`jnl`	Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. CoRR Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
2018	J	`jnl`	Quantum security proofs using semi-classical oracles. IACR Cryptol. ePrint Arch. Andris Ambainis, Mike Hamburg, Dominique Unruh
2017	J	`jnl`	All Classical Adversary Methods are Equivalent for Total Functions. CoRR Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
2017	J	`jnl`	All Classical Adversary Methods are Equivalent for Total Functions. Electron. Colloquium Comput. Complex. Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
2017	B	`conf`	Exact Quantum Query Complexity of \text EXACT_k, l^n. SOFSEM Andris Ambainis, Janis Iraids, Daniel Nagaj
2017	J	`jnl`	Optimal one-shot quantum algorithm for EQUALITY and AND. CoRR Andris Ambainis, Janis Iraids
2017	A*	`conf`	Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. STOC Andris Ambainis, Martins Kokainis
2017	J	`jnl`	Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. CoRR Andris Ambainis, Martins Kokainis
2017	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. J. ACM Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2017	J	`jnl`	Understanding Quantum Algorithms via Query Complexity. CoRR Andris Ambainis
2016	A*	`conf`	Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
2016	J	`jnl`	Exact quantum query complexity of EXACT CoRR Andris Ambainis, Janis Iraids, Daniel Nagaj
2016	J	`jnl`	Four Collaborations with Rūsiņš Freivalds. Balt. J. Mod. Comput. Andris Ambainis
2016	A	`conf`	Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. CCC Andris Ambainis, Martins Kokainis, Robin Kothari
2016	J	`jnl`	Optimal One-shot Quantum Algorithm for EQUALITY and AND. Balt. J. Mod. Comput. Andris Ambainis, Janis Iraids
2016	J	`jnl`	Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. CoRR Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai
2016	A	`conf`	Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CCC Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
2016	—	`ch.`	Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms Andris Ambainis
2016	—	`ch.`	Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms Andris Ambainis
2016	J	`jnl`	Quantum Query Complexity of Almost All Functions with Fixed On-set Size. Comput. Complex. Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2016	J	`jnl`	Rūsiņš Mārtiņš Freivalds (1942-2016). Bull. EATCS Andris Ambainis
2016	Misc	`conf`	Sensitivity Versus Certificate Complexity of Boolean Functions. CSR Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
2016	A*	`conf`	Separations in query complexity based on pointer functions. STOC Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2016	J	`jnl`	Superlinear Advantage for Exact Quantum Algorithms. SIAM J. Comput. Andris Ambainis
2015	J	`jnl`	Almost quadratic gap between partition complexity and query/communication complexity. CoRR Andris Ambainis, Martins Kokainis
2015	J	`jnl`	Almost quadratic gap between partition complexity and query/communication complexity. Electron. Colloquium Comput. Complex. Andris Ambainis
2015	J	`jnl`	Automata and Quantum Computing. CoRR Andris Ambainis, Abuzer Yakaryilmaz
2015	J	`jnl`	Correcting for potential barriers in quantum walk search. Quantum Inf. Comput. Andris Ambainis, Thomas G. Wong
2015	J	`jnl`	Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
2015	J	`jnl`	Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Inf. Comput. Andris Ambainis, Jozef Gruska, Shenggen Zheng
2015	A*	`conf`	Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. STOC Andris Ambainis, Yuval Filmus, François Le Gall
2015	A*	`conf`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC Scott Aaronson, Andris Ambainis
2015	J	`jnl`	Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems. ACM Trans. Comput. Theory Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2015	J	`jnl`	Optimal Classical Random Access Codes Using Single d-level Systems. CoRR Andris Ambainis, Dmitry Kravchenko, Ashutosh Rai
2015	J	`jnl`	Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
2015	J	`jnl`	Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Electron. Colloquium Comput. Complex. Andris Ambainis
2015	J	`jnl`	Sensitivity versus Certificate Complexity of Boolean Functions. CoRR Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
2015	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. CoRR Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2015	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2015	C	`conf`	Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. TAMC Andris Ambainis, Jevgenijs Vihrovs
2015	J	`jnl`	Spatial search on grids with minimum memory. Quantum Inf. Comput. Andris Ambainis, Renato Portugal, Nikolay Nahimov
2014	—	`conf`	A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. MFCS (2) Andris Ambainis, Krisjanis Prusis
2014	J	`jnl`	A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. CoRR Krisjanis Prusis, Andris Ambainis
2014	J	`jnl`	A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Electron. Colloquium Comput. Complex. Andris Ambainis, Krisjanis Prusis
2014	J	`jnl`	Exact query complexity of some special classes of Boolean functions. CoRR Andris Ambainis, Jozef Gruska, Shenggen Zheng
2014	J	`jnl`	Fast Matrix Multiplication: Limitations of the Laser Method. CoRR Andris Ambainis, Yuval Filmus, François Le Gall
2014	J	`jnl`	Fast Matrix Multiplication: Limitations of the Laser Method. Electron. Colloquium Comput. Complex. Andris Ambainis, Yuval Filmus, François Le Gall
2014	J	`jnl`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR Scott Aaronson, Andris Ambainis
2014	J	`jnl`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis
2014	J	`jnl`	How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Comput. Complex. Andris Ambainis, Ronald de Wolf
2014	A	`conf`	On Physical Problems that are Slightly More Difficult than QMA. CCC Andris Ambainis
2014	J	`jnl`	Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. CoRR Andris Ambainis, Ansis Rosmanis, Dominique Unruh
2014	J	`jnl`	Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. IACR Cryptol. ePrint Arch. Andris Ambainis, Ansis Rosmanis, Dominique Unruh
2014	A*	`conf`	Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. FOCS Andris Ambainis, Ansis Rosmanis, Dominique Unruh
2014	J	`jnl`	Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Inf. Comput. Andris Ambainis, Ashley Montanaro
2014	—	`conf`	Recent Developments in Quantum Algorithms and Complexity. DCFS Andris Ambainis
2014	J	`jnl`	Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. CoRR Andris Ambainis, Jevgenijs Vihrovs
2014	J	`jnl`	Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. Electron. Colloquium Comput. Complex. Andris Ambainis, Jevgenijs Vihrovs
2014	J	`jnl`	The Need for Structure in Quantum Speedups. Theory Comput. Scott Aaronson, Andris Ambainis
2014	J	`jnl`	Tighter Relations Between Sensitivity and Other Complexity Measures. CoRR Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
2014	J	`jnl`	Tighter Relations Between Sensitivity and Other Complexity Measures. Electron. Colloquium Comput. Complex. Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
2014	—	`conf`	Tighter Relations between Sensitivity and Other Complexity Measures. ICALP (1) Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
2014	—	`conf`	Weak Parity. ICALP (1) Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2013	—	`conf`	Exact Quantum Query Complexity of EXACT and THRESHOLD. TQC Andris Ambainis, Janis Iraids, Juris Smotrovs
2013	J	`jnl`	Exact quantum query complexity of EXACT and THRESHOLD CoRR Andris Ambainis, Janis Iraids, Juris Smotrovs
2013	A	`conf`	How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? CCC Andris Ambainis, Ronald de Wolf
2013	J	`jnl`	New upper bound on block sensitivity and certificate complexity in terms of sensitivity. CoRR Andris Ambainis, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
2013	J	`jnl`	On physical problems that are slightly more difficult than QMA. CoRR Andris Ambainis
2013	J	`jnl`	On symmetric nonlocal games. Theor. Comput. Sci. Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov, Alexander Rivosh, Madars Virza
2013	A	`conf`	Optimal quantum query bounds for almost all Boolean functions. STACS Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf
2013	J	`jnl`	Parameterized Quantum Query Complexity of Graph Collision CoRR Andris Ambainis, Kaspars Balodis, Janis Iraids, Raitis Ozols, Juris Smotrovs
2013	—	`conf`	Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. TQC Andris Ambainis, Janis Iraids
2013	A*	`conf`	Superlinear advantage for exact quantum algorithms. STOC Andris Ambainis
2013	J	`jnl`	Weak Parity. CoRR Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2013	J	`jnl`	Weak Parity. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2013	B	`conf`	Worst Case Analysis of Non-local Games. SOFSEM Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza
2012	J	`jnl`	A quantum lovász local lemma. J. ACM Andris Ambainis, Julia Kempe, Or Sattath
2012	—	`conf`	Advantage of Quantum Strategies in Random Symmetric XOR Games. MEMICS Andris Ambainis, Janis Iraids, Dmitry Kravchenko, Madars Virza
2012	—	`conf`	Grover's Algorithm with Errors. MEMICS Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh
2012	—	`conf`	Quantum Strategies Are Better Than Classical in Almost Any XOR Game. ICALP (1) Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs, Madars Virza
2012	—	`conf`	Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. TQC Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh
2012	J	`jnl`	Superiority of exact quantum automata for promise problems. Inf. Process. Lett. Andris Ambainis, Abuzer Yakaryilmaz
2012	J	`jnl`	Superlinear advantage for exact quantum algorithms CoRR Andris Ambainis
2012	A	`conf`	Variable time amplitude amplification and quantum algorithms for linear algebra problems. STACS Andris Ambainis
2011	J	`jnl`	New separation between Electron. Colloquium Comput. Complex. Andris Ambainis, Xiaoming Sun
2011	J	`jnl`	New separation between $s(f)$ and $bs(f)$ CoRR Andris Ambainis, Xiaoming Sun
2011	—	`conf`	Quantum Finite Automata. NCMA Andris Ambainis
2011	—	`conf`	Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
2011	J	`jnl`	Quantum strategies are better than classical in almost any XOR game CoRR Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs, Madars Virza
2011	J	`jnl`	Search by quantum walks on two-dimensional grid without amplitude amplification CoRR Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh
2011	A	`conf`	Symmetry-Assisted Adversaries for Quantum State Generation. CCC Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland
2011	A	`conf`	The Need for Structure in Quantum Speedups. ICS Scott Aaronson, Andris Ambainis
2010	J	`jnl`	A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. Theory Comput. Andris Ambainis
2010	A*	`conf`	A quantum lovász local lemma. STOC Andris Ambainis, Julia Kempe, Or Sattath
2010	J	`jnl`	Any AND-OR Formula of Size N Can Be Evaluated in Time N SIAM J. Comput. Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang
2010	J	`jnl`	Limits on entropic uncertainty relations. Quantum Inf. Comput. Andris Ambainis
2010	J	`jnl`	New Developments in Quantum Algorithms CoRR Andris Ambainis
2010	B	`conf`	New Developments in Quantum Algorithms. MFCS Andris Ambainis
2010	C	`conf`	Nonlocal Quantum XOR Games for Large Number of Players. TAMC Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh
2010	J	`jnl`	Quantum Search with Variable Times. Theory Comput. Syst. Andris Ambainis
2010	J	`jnl`	Quantum algorithms for formula evaluation CoRR Andris Ambainis
2010	—	`ch.`	Quantum algorithms for formula evaluation. Quantum Cryptography and Computing Andris Ambainis
2010	J	`jnl`	Quantum property testing for bounded-degree graphs CoRR Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
2010	J	`jnl`	Symmetry-assisted adversaries for quantum state generation CoRR Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland
2010	J	`jnl`	Symmetry-assisted adversaries for quantum state generation. Electron. Colloquium Comput. Complex. Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland
2010	J	`jnl`	The quantum query complexity of certification. Quantum Inf. Comput. Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
2010	J	`jnl`	Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations CoRR Andris Ambainis
2009	J	`jnl`	A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica Andris Ambainis, Robert Spalek, Ronald de Wolf
2009	J	`jnl`	A Quantum Lovasz Local Lemma CoRR Andris Ambainis, Julia Kempe, Or Sattath
2009	J	`jnl`	Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size CoRR Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2009	J	`jnl`	Improved constructions of quantum automata. Theor. Comput. Sci. Andris Ambainis, Nikolajs Nahimovs
2009	J	`jnl`	The Need for Structure in Quantum Speedups CoRR Scott Aaronson, Andris Ambainis
2009	J	`jnl`	The Need for Structure in Quantum Speedups. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis
2009	J	`jnl`	The quantum query complexity of certification CoRR Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
2008	—	`conf`	Improved Constructions of Quantum Automata. TQC Andris Ambainis, Nikolajs Nahimovs
2008	J	`jnl`	Probabilistic and team PFIN-type learning: General properties. J. Comput. Syst. Sci. Andris Ambainis
2008	—	`ch.`	Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms Andris Ambainis
2008	—	`ch.`	Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms Andris Ambainis
2008	B	`conf`	Quantum Query Complexity of Boolean Functions with Small On-Sets. ISAAC Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2008	B	`conf`	Quantum Random Walks - New Method for Designing Quantum Algorithms. SOFSEM Andris Ambainis
2008	B	`conf`	Quantum Walks with Multiple or Moving Marked Locations. SOFSEM Andris Ambainis, Alexander Rivosh
2008	A	`conf`	Quantum search with variable times. STACS Andris Ambainis
2007	A*	`conf`	Any AND-OR Formula of Size N can be Evaluated in time N FOCS Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang
2007	J	`jnl`	Improved algorithms for quantum identification of Boolean oracles. Theor. Comput. Sci. Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, Shigeru Yamashita
2007	J	`jnl`	Quantum Walk Algorithm for Element Distinctness. SIAM J. Comput. Andris Ambainis
2007	A	`conf`	Quantum t-designs: t-wise Independence in the Quantum World. CCC Andris Ambainis, Joseph Emerson
2007	J	`jnl`	Quantum t-designs: t-wise independence in the quantum world. Electron. Colloquium Comput. Complex. Andris Ambainis, Joseph Emerson
2006	A*	`conf`	A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. STOC Andris Ambainis, Robert Spalek, Ronald de Wolf
2006	J	`jnl`	Algebraic Results on Quantum Automata. Theory Comput. Syst. Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien
2006	J	`jnl`	Computing with highly mixed states. J. ACM Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani
2006	—	`conf`	Improved Algorithms for Quantum Identification of Boolean Oracles. SWAT Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond Harry Putra, Shigeru Yamashita
2006	B	`conf`	Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems. ISAAC Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2006	J	`jnl`	Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci. Andris Ambainis
2006	A	`conf`	Quantum Algorithms for Matching and Network Flows. STACS Andris Ambainis, Robert Spalek
2006	J	`jnl`	The minimum distance problem for two-way entanglement purification. IEEE Trans. Inf. Theory Andris Ambainis, Daniel Gottesman
2005	J	`jnl`	A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs CoRR Andris Ambainis, Robert Spalek, Ronald de Wolf
2005	J	`jnl`	A new quantum lower bound method, with an application to strong direct product theorem for quantum search CoRR Andris Ambainis
2005	A*	`conf`	Coins make quantum walks faster. SODA Andris Ambainis, Julia Kempe, Alexander Rivosh
2005	J	`jnl`	Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. Theory Comput. Andris Ambainis
2005	J	`jnl`	Probabilistic and Team PFIN-type Learning: General Properties CoRR Andris Ambainis
2005	J	`jnl`	Quantum Search of Spatial Regions. Theory Comput. Scott Aaronson, Andris Ambainis
2005	J	`jnl`	Quantum search algorithms CoRR Andris Ambainis
2004	J	`jnl`	A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci. Andris Ambainis
2004	A	`conf`	Algebraic Results on Quantum Automata. STACS Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien
2004	—	`conf`	Cryptographic Randomized Response Techniques. Public Key Cryptography Andris Ambainis, Markus Jakobsson, Helger Lipmaa
2004	J	`jnl`	Distributed construction of quantum fingerprints. Quantum Inf. Comput. Andris Ambainis, Yaoyun Shi
2004	J	`jnl`	Lower bounds on the Deterministic and Quantum Communication Complexity of HAM Electron. Colloquium Comput. Complex. Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2004	J	`jnl`	Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance CoRR Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2004	A	`conf`	Multiparty Quantum Coin Flipping. CCC Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig
2004	J	`jnl`	Parsimony hierarchies for inductive inference. J. Symb. Log. Andris Ambainis, John Case, Sanjay Jain, Mandayam Suraj
2004	A	`conf`	Quantum Identification of Boolean Oracles. STACS Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita
2004	A*	`conf`	Quantum Walk Algorithm for Element Distinctness. FOCS Andris Ambainis
2004	A*	`conf`	Quantum algorithms a decade after shor. STOC Andris Ambainis
2004	J	`jnl`	Quantum search algorithms. SIGACT News Andris Ambainis
2004	—	`conf`	Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. APPROX-RANDOM Andris Ambainis, Adam D. Smith
2004	A	`conf`	Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. CCC Andris Ambainis, Ke Yang
2003	J	`jnl`	Cryptographic Randomized Response Techniques CoRR Andris Ambainis, Markus Jakobsson, Helger Lipmaa
2003	J	`jnl`	Cryptographic Randomized Response Techniques. IACR Cryptol. ePrint Arch. Andris Ambainis, Markus Jakobsson, Helger Lipmaa
2003	J	`jnl`	Exact results for accepting probabilities of quantum automata. Theor. Comput. Sci. Andris Ambainis, Arnolds Kikusts
2003	J	`jnl`	Multiparty Quantum Coin Flipping CoRR Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig
2003	A*	`conf`	Polynomial Degree vs. Quantum Query Complexity. FOCS Andris Ambainis
2003	J	`jnl`	Polynomial degree vs. quantum query complexity CoRR Andris Ambainis
2003	A*	`conf`	Quantum Search of Spatial Regions. FOCS Scott Aaronson, Andris Ambainis
2003	—	`conf`	Size of Quantum Versus Deterministic Finite Automata. VLSI Andris Ambainis, Uldis Barbans, Agnese Belousova, Aleksandrs Belovs, Ilze Dzelme, Girts Folkmanis, Rusins Freivalds, Peteris Ledins, Rihards Opmanis, Agnis Skuskovniks
2003	J	`jnl`	The Quantum Communication Complexity of Sampling. SIAM J. Comput. Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
2003	J	`jnl`	Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information Electron. Colloquium Comput. Complex. Andris Ambainis, Ke Yang
2002	J	`jnl`	Delayed Binary Search, or Playing Twenty Questions with a Procrastinator. Algorithmica Andris Ambainis, Stephen A. Bloch, David L. Schweizer
2002	J	`jnl`	Dense quantum coding and quantum finite automata. J. ACM Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
2002	A	`conf`	Extracting Quantum Entanglement. CCC Andris Ambainis, Adam D. Smith, Ke Yang
2002	J	`jnl`	Quantum Lower Bounds by Quantum Arguments. J. Comput. Syst. Sci. Andris Ambainis
2002	J	`jnl`	ROM-based computation: quantum versus classical. Quantum Inf. Comput. Benjamin C. Travaglione, Michael A. Nielsen, Howard M. Wiseman, Andris Ambainis
2002	J	`jnl`	Two-way finite automata with quantum and classical state. Theor. Comput. Sci. Andris Ambainis, John Watrous
2001	A*	`conf`	A new protocol and lower bounds for quantum coin flipping. STOC Andris Ambainis
2001	B	`conf`	Exact Results for Accepting Probabilities of Quantum Automata. MFCS Andris Ambainis, Arnolds Kikusts
2001	J	`jnl`	Hierarchies of probabilistic and team FIN-learning. Theor. Comput. Sci. Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, Carl H. Smith
2001	J	`jnl`	On learning formulas in the limit and with assurance. Inf. Process. Lett. Andris Ambainis
2001	A	`conf`	On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. STACS Andris Ambainis, Arnolds Kikusts, Maris Valdats
2001	A*	`conf`	One-dimensional quantum walks. STOC Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
2001	J	`jnl`	Probabilistic inductive inference: a survey. Theor. Comput. Sci. Andris Ambainis
2001	—	`conf`	Quantum query algorithms and lower bounds. FotFS Andris Ambainis
2001	A*	`conf`	Quantum walks on graphs. STOC Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani
2001	J	`jnl`	The Communication Complexity of Enumeration, Elimination, and Selection Electron. Colloquium Comput. Complex. Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2001	J	`jnl`	The Communication Complexity of Enumeration, Elimination, and Selection. J. Comput. Syst. Sci. Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2000	A	`conf`	Average-Case Quantum Query Complexity. STACS Andris Ambainis, Ronald de Wolf
2000	A*	`conf`	Computing with highly mixed states (extended abstract). STOC Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani
2000	J	`jnl`	How rich is the structure of the intrinsic complexity of learning. Inf. Process. Lett. Andris Ambainis
2000	B	`conf`	Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. LATIN Andris Ambainis, Satyanarayana V. Lokam
2000	A*	`conf`	Private Quantum Channels. FOCS Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf
2000	J	`jnl`	Quantum lower bounds by quantum arguments CoRR Andris Ambainis
2000	A*	`conf`	Quantum lower bounds by quantum arguments. STOC Andris Ambainis
2000	A	`conf`	The Communication Complexity of Enumeration, Elimination, and Selection. CCC Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
1999	A*	`conf`	A Better Lower Bound for Quantum Algorithms Searching an Ordered List. FOCS Andris Ambainis
1999	J	`jnl`	A Note on Quantum Black-Box Complexity of Almost all Boolean Functions. Inf. Process. Lett. Andris Ambainis
1999	J	`jnl`	A better lower bound for quantum algorithms searching an ordered list CoRR Andris Ambainis
1999	J	`jnl`	Average-Case Quantum Query Complexity CoRR Andris Ambainis, Ronald de Wolf
1999	J	`jnl`	Bounded Depth Arithmetic Circuits: Counting and Closure Electron. Colloquium Comput. Complex. Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999	A*	`conf`	Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999	A*	`conf`	Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
1999	J	`jnl`	Inductive Inference with Procrastination: Back to Definitions. Fundam. Informaticae Andris Ambainis, Rusins Freivalds, Carl H. Smith
1999	J	`jnl`	Ordinal Mind Change Complexity of Language Identification. Theor. Comput. Sci. Andris Ambainis, Sanjay Jain, Arun Sharma
1999	A*	`conf`	Playing Twenty Questions with a Procrastinator. SODA Andris Ambainis, Stephen A. Bloch, David L. Schweizer
1999	J	`jnl`	Probabilistic Inductive Inference:a Survey CoRR Andris Ambainis
1999	Misc	`conf`	Probabilities to Accept Languages by Quantum Finite Automata. COCOON Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts
1999	J	`jnl`	Probabilities to accept languages by quantum finite automata CoRR Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts
1999	B	`conf`	Quantum Finite Multitape Automata. SOFSEM Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski
1999	J	`jnl`	Two-way finite automata with quantum and classical states CoRR Andris Ambainis, John Watrous
1998	A*	`conf`	1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. FOCS Andris Ambainis, Rusins Freivalds
1998	J	`jnl`	1-way quantum finite automata: strengths, weaknesses and generalizations CoRR Andris Ambainis, Rusins Freivalds
1998	J	`jnl`	A note on quantum black-box complexity of almost all Boolean functions CoRR Andris Ambainis
1998	J	`jnl`	Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata CoRR Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
1998	B	`conf`	On Counting AC MFCS Andris Ambainis, David A. Mix Barrington, Huong LeThanh
1998	J	`jnl`	On Counting AC Electron. Colloquium Comput. Complex. Andris Ambainis, David A. Mix Barrington, Huong LeThanh
1998	A*	`conf`	The Quantum Communication Complexity of Sampling. FOCS Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
1997	B	`conf`	Effects of Kolmogorov Complexity Present in Inductive Inference as Well. ALT Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs
1997	A*	`conf`	Nearly Tight Bounds on the Learnability of Evolution. FOCS Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan
1997	—	`conf`	Ordinal Mind Change Complexity of Language Identification. EuroCOLT Andris Ambainis, Sanjay Jain, Arun Sharma
1997	B	`conf`	Team Learning as a Game. ALT Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, William I. Gasarch, Carl H. Smith
1997	A*	`conf`	Upper Bound on Communication Complexity of Private Information Retrieval. ICALP Andris Ambainis
1997	—	`conf`	Weak and Strong Recognition by 2-way Randomized Automata. RANDOM Andris Ambainis, Rusins Freivalds, Marek Karpinski
1996	J	`jnl`	Communication Complexity in a 3-Computer Model. Algorithmica Andris Ambainis
1996	A	`conf`	General Inductive Inference Types Based on Linearly-Ordered Sets. STACS Andris Ambainis, Rusins Freivalds, Carl H. Smith
1996	A*	`conf`	Probabilistic and Team PFIN-Type Learning: General Properties. COLT Andris Ambainis
1996	B	`conf`	The Complexity of Probabilistic versus Deterministic Finite Automata. ISAAC Andris Ambainis
1996	B	`conf`	Transformations that Preserve Learnability. ALT Andris Ambainis, Rusins Freivalds
1996	A	`conf`	Upper Bounds on Multiparty Communication Complexity of Shifts. STACS Andris Ambainis
1996	J	`jnl`	Upper bound on the communication complexity of private information retrieval. IACR Cryptol. ePrint Arch. Andris Ambainis
1995	B	`conf`	Application of Kolmogorov Complexity to Inductive Inference with Limited Memory. ALT Andris Ambainis
1995	—	`conf`	Optimization Problem in Inductive Inference. GOSLER Final Report Andris Ambainis
1995	—	`conf`	The power of procrastination in inductive inference: How it depends on used ordinal notations. EuroCOLT Andris Ambainis
1994	—	`conf`	Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference. AII/ALT Andris Ambainis, Juris Smotrovs