| 2023 | SOFSEM | Quantum Complexity for Vector Domination Problem. | Andris Ambainis, Ansis Zvirbulis |
| 2020 | MFCS | Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. | Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs |
| 2020 | STOC | Quadratic speedup for finding marked vertices by quantum walks. | Andris Ambainis, Andrs Gilyn, Stacey Jeffery, Martins Kokainis |
| 2019 | CRYPTO | Quantum Security Proofs Using Semi-classical Oracles. | Andris Ambainis, Mike Hamburg, Dominique Unruh |
| 2019 | SODA | Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. | Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs |
| 2018 | STACS | All Classical Adversary Methods are Equivalent for Total Functions. | Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs |
| 2018 | SOFSEM | Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test. | Farid M. Ablayev, Andris Ambainis, Kamil Khadiev, Aliya Khadieva |
| 2017 | STOC | Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. | Andris Ambainis, Martins Kokainis |
| 2017 | SOFSEM | Exact Quantum Query Complexity of \text EXACT_k, l^n. | Andris Ambainis, Janis Iraids, Daniel Nagaj |
| 2016 | CSR | Sensitivity Versus Certificate Complexity of Boolean Functions. | Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs |
| 2016 | SODA | Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. | Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf |
| 2016 | STOC | Separations in query complexity based on pointer functions. | Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs |
| 2015 | STOC | Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. | Scott Aaronson, Andris Ambainis |
| 2015 | STOC | Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. | Andris Ambainis, Yuval Filmus, Franois Le Gall |
| 2015 | TAMC | Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. | Andris Ambainis, Jevgenijs Vihrovs |
| 2014 | FOCS | Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. | Andris Ambainis, Ansis Rosmanis, Dominique Unruh |
| 2014 | ICALP | Weak Parity. | Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian |
| 2014 | ICALP | Tighter Relations between Sensitivity and Other Complexity Measures. | Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo |
| 2014 | MFCS | A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. | Andris Ambainis, Krisjanis Prusis |
| 2013 | STOC | Superlinear advantage for exact quantum algorithms. | Andris Ambainis |
| 2013 | STACS | Optimal quantum query bounds for almost all Boolean functions. | Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf |
| 2013 | SOFSEM | Worst Case Analysis of Non-local Games. | Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza |
| 2012 | ICALP | Quantum Strategies Are Better Than Classical in Almost Any XOR Game. | Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs, Madars Virza |
| 2012 | STACS | Variable time amplitude amplification and quantum algorithms for linear algebra problems. | Andris Ambainis |
| 2010 | MFCS | New Developments in Quantum Algorithms. | Andris Ambainis |
| 2010 | STOC | A quantum lovsz local lemma. | Andris Ambainis, Julia Kempe, Or Sattath |
| 2010 | TAMC | Nonlocal Quantum XOR Games for Large Number of Players. | Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh |
| 2008 | ISAAC | Quantum Query Complexity of Boolean Functions with Small On-Sets. | Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita |
| 2008 | STACS | Quantum search with variable times. | Andris Ambainis |
| 2008 | SOFSEM | Quantum Random Walks - New Method for Designing Quantum Algorithms. | Andris Ambainis |
| 2008 | SOFSEM | Quantum Walks with Multiple or Moving Marked Locations. | Andris Ambainis, Alexander Rivosh |
| 2007 | FOCS | Any AND-OR Formula of Size N can be Evaluated in time N | Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang |
| 2006 | ISAAC | Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems. | Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis |
| 2006 | STOC | A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. | Andris Ambainis, Robert Spalek, Ronald de Wolf |
| 2006 | STACS | Quantum Algorithms for Matching and Network Flows. | Andris Ambainis, Robert Spalek |
| 2005 | SODA | Coins make quantum walks faster. | Andris Ambainis, Julia Kempe, Alexander Rivosh |
| 2004 | FOCS | Quantum Walk Algorithm for Element Distinctness. | Andris Ambainis |
| 2004 | PKC | Cryptographic Randomized Response Techniques. | Andris Ambainis, Markus Jakobsson, Helger Lipmaa |
| 2004 | STOC | Quantum algorithms a decade after shor. | Andris Ambainis |
| 2004 | STACS | Algebraic Results on Quantum Automata. | Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thrien |
| 2004 | STACS | Quantum Identification of Boolean Oracles. | Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita |
| 2003 | FOCS | Quantum Search of Spatial Regions. | Scott Aaronson, Andris Ambainis |
| 2003 | FOCS | Polynomial Degree vs. Quantum Query Complexity. | Andris Ambainis |
| 2001 | MFCS | Exact Results for Accepting Probabilities of Quantum Automata. | Andris Ambainis, Arnolds Kikusts |
| 2001 | STOC | A new protocol and lower bounds for quantum coin flipping. | Andris Ambainis |
| 2001 | STOC | One-dimensional quantum walks. | Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous |
| 2001 | STOC | Quantum walks on graphs. | Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani |
| 2001 | STACS | On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. | Andris Ambainis, Arnolds Kikusts, Maris Valdats |
| 2000 | FOCS | Private Quantum Channels. | Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf |
| 2000 | LATIN | Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. | Andris Ambainis, Satyanarayana V. Lokam |
| 2000 | STOC | Quantum lower bounds by quantum arguments. | Andris Ambainis |
| 2000 | STOC | Computing with highly mixed states (extended abstract). | Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani |
| 2000 | STACS | Average-Case Quantum Query Complexity. | Andris Ambainis, Ronald de Wolf |
| 1999 | COCOON | Probabilities to Accept Languages by Quantum Finite Automata. | Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts |
| 1999 | FOCS | A Better Lower Bound for Quantum Algorithms Searching an Ordered List. | Andris Ambainis |
| 1999 | ICALP | Bounded Depth Arithmetic Circuits: Counting and Closure. | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh |
| 1999 | SODA | Playing Twenty Questions with a Procrastinator. | Andris Ambainis, Stephen A. Bloch, David L. Schweizer |
| 1999 | STOC | Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. | Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani |
| 1999 | SOFSEM | Quantum Finite Multitape Automata. | Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski |
| 1998 | FOCS | 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. | Andris Ambainis, Rusins Freivalds |
| 1998 | FOCS | The Quantum Communication Complexity of Sampling. | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
| 1998 | MFCS | On Counting AC | Andris Ambainis, David A. Mix Barrington, Huong LeThanh |
| 1997 | ALT | Effects of Kolmogorov Complexity Present in Inductive Inference as Well. | Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs |
| 1997 | ALT | Team Learning as a Game. | Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, William I. Gasarch, Carl H. Smith |
| 1997 | FOCS | Nearly Tight Bounds on the Learnability of Evolution. | Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan |
| 1997 | ICALP | Upper Bound on Communication Complexity of Private Information Retrieval. | Andris Ambainis |
| 1996 | ALT | Transformations that Preserve Learnability. | Andris Ambainis, Rusins Freivalds |
| 1996 | COLT | Probabilistic and Team PFIN-Type Learning: General Properties. | Andris Ambainis |
| 1996 | ISAAC | The Complexity of Probabilistic versus Deterministic Finite Automata. | Andris Ambainis |
| 1996 | STACS | Upper Bounds on Multiparty Communication Complexity of Shifts. | Andris Ambainis |
| 1996 | STACS | General Inductive Inference Types Based on Linearly-Ordered Sets. | Andris Ambainis, Rusins Freivalds, Carl H. Smith |
| 1995 | ALT | Application of Kolmogorov Complexity to Inductive Inference with Limited Memory. | Andris Ambainis |
| 1994 | ALT | Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference. | Andris Ambainis, Juris Smotrovs |