Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference. - Andris Ambainis; Juris Smotrovs (AII/ALT, 1994)

Application of Kolmogorov Complexity to Inductive Inference with Limited Memory. - Andris Ambainis (ALT, 1995)

The power of procrastination in inductive inference: How it depends on used ordinal notations. - Andris Ambainis (EuroCOLT, 1995)

Optimization Problem in Inductive Inference. - Andris Ambainis (GOSLER Final Report, 1995)

Transformations that Preserve Learnability. - Andris Ambainis; Rusins Freivalds (ALT, 1996)

The Complexity of Probabilistic versus Deterministic Finite Automata. - Andris Ambainis (ISAAC, 1996)

Upper Bounds on Multiparty Communication Complexity of Shifts. - Andris Ambainis (STACS, 1996)

General Inductive Inference Types Based on Linearly-Ordered Sets. - Andris Ambainis; Rusins Freivalds; Carl H. Smith (STACS, 1996)

Communication Complexity in a 3-Computer Model. - Andris Ambainis (Algorithmica, 1996)

Upper bound on the communication complexity of private information retrieval. - Andris Ambainis (IACR Cryptol. ePrint Arch., 1996)

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 (ALT, 1997)

Team Learning as a Game. - Andris Ambainis; Kalvis Apsitis; Rusins Freivalds; William I. Gasarch; Carl H. Smith (ALT, 1997)

Nearly Tight Bounds on the Learnability of Evolution. - Andris Ambainis; Richard Desper; Martin Farach; Sampath Kannan (FOCS, 1997)

Weak and Strong Recognition by 2-way Randomized Automata. - Andris Ambainis; Rusins Freivalds; Marek Karpinski (RANDOM, 1997)

1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. - Andris Ambainis; Rusins Freivalds (FOCS, 1998)

On Counting AC0 Circuits with Negative Constants - Andris Ambainis; David A. Mix Barrington; Huong LeThanh (Electron. Colloquium Comput. Complex., 1998)

Probabilities to Accept Languages by Quantum Finite Automata. - Andris Ambainis; Richard F. Bonner; Rusins Freivalds; Arnolds Kikusts (COCOON, 1999)

A Better Lower Bound for Quantum Algorithms Searching an Ordered List. - Andris Ambainis (FOCS, 1999)

Playing Twenty Questions with a Procrastinator. - Andris Ambainis; Stephen A. Bloch; David L. Schweizer (SODA, 1999)

Quantum Finite Multitape Automata. - Andris Ambainis; Richard F. Bonner; Rusins Freivalds; Marats Golovkins; Marek Karpinski (SOFSEM, 1999)

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. - Andris Ambainis; Ashwin Nayak 001; Amnon Ta-Shma; Umesh V. Vazirani (STOC, 1999)

Two-way finite automata with quantum and classical states - Andris Ambainis; John Watrous (CoRR, 1999)

Probabilistic Inductive Inference:a Survey - Andris Ambainis (CoRR, 1999)

Bounded Depth Arithmetic Circuits: Counting and Closure - Eric Allender; Andris Ambainis; David A. Mix Barrington; Samir Datta; Huong LeThanh (Electron. Colloquium Comput. Complex., 1999)

Inductive Inference with Procrastination: Back to Definitions. - Andris Ambainis; Rusins Freivalds; Carl H. Smith (Fundam. Informaticae, 1999)

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

Ordinal Mind Change Complexity of Language Identification. - Andris Ambainis; Sanjay Jain 001; Arun Sharma 001 (Theor. Comput. Sci., 1999)

Private Quantum Channels. - Andris Ambainis; Michele Mosca; Alain Tapp; Ronald de Wolf (FOCS, 2000)

Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. - Andris Ambainis; Satyanarayana V. Lokam (LATIN, 2000)

Average-Case Quantum Query Complexity. - Andris Ambainis; Ronald de Wolf (STACS, 2000)

Computing with highly mixed states (extended abstract). - Andris Ambainis; Leonard J. Schulman; Umesh V. Vazirani (STOC, 2000)

How rich is the structure of the intrinsic complexity of learning. - Andris Ambainis (Inf. Process. Lett., 2000)

Quantum query algorithms and lower bounds. - Andris Ambainis (FotFS, 2001)

On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. - Andris Ambainis; Arnolds Kikusts; Maris Valdats (STACS, 2001)

One-dimensional quantum walks. - Andris Ambainis; Eric Bach 001; Ashwin Nayak 001; Ashvin Vishwanath; John Watrous (STOC, 2001)

Quantum walks on graphs. - Dorit Aharonov; Andris Ambainis; Julia Kempe; Umesh V. Vazirani (STOC, 2001)

On learning formulas in the limit and with assurance. - Andris Ambainis (Inf. Process. Lett., 2001)

The Communication Complexity of Enumeration, Elimination, and Selection. - Andris Ambainis; Harry Buhrman; William I. Gasarch; Bala Kalyanasundaram; Leen Torenvliet (J. Comput. Syst. Sci., 2001)

Probabilistic inductive inference: a survey. - Andris Ambainis (Theor. Comput. Sci., 2001)

Hierarchies of probabilistic and team FIN-learning. - Andris Ambainis; Kalvis Apsitis; Rusins Freivalds; Carl H. Smith (Theor. Comput. Sci., 2001)

Extracting Quantum Entanglement. - Andris Ambainis; Adam D. Smith 001; Ke Yang 005 (CCC, 2002)

Delayed Binary Search, or Playing Twenty Questions with a Procrastinator. - Andris Ambainis; Stephen A. Bloch; David L. Schweizer (Algorithmica, 2002)

Dense quantum coding and quantum finite automata. - Andris Ambainis; Ashwin Nayak 001; Amnon Ta-Shma; Umesh V. Vazirani (J. ACM, 2002)

Quantum Lower Bounds by Quantum Arguments. - Andris Ambainis (J. Comput. Syst. Sci., 2002)

ROM-based computation: quantum versus classical. - Benjamin C. Travaglione; Michael A. Nielsen; Howard M. Wiseman; Andris Ambainis (Quantum Inf. Comput., 2002)

Two-way finite automata with quantum and classical state. - Andris Ambainis; John Watrous (Theor. Comput. Sci., 2002)

Size of Quantum Versus Deterministic Finite Automata. - Andris Ambainis; Uldis Barbans; Agnese Belousova; Aleksandrs Belovs; Ilze Dzelme; Girts Folkmanis; Rusins Freivalds; Peteris Ledins; Rihards Opmanis; Agnis Skuskovniks (VLSI, 2003)

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information - Andris Ambainis; Ke Yang (Electron. Colloquium Comput. Complex., 2003)

Cryptographic Randomized Response Techniques. - Andris Ambainis; Markus Jakobsson; Helger Lipmaa (IACR Cryptol. ePrint Arch., 2003)

The Quantum Communication Complexity of Sampling. - Andris Ambainis; Leonard J. Schulman; Amnon Ta-Shma; Umesh V. Vazirani; Avi Wigderson (SIAM J. Comput., 2003)

Exact results for accepting probabilities of quantum automata. - Andris Ambainis; Arnolds Kikusts (Theor. Comput. Sci., 2003)

Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. - Andris Ambainis; Adam D. Smith 001 (APPROX-RANDOM, 2004)

Multiparty Quantum Coin Flipping. - Andris Ambainis; Harry Buhrman; Yevgeniy Dodis; Hein Röhrig (CCC, 2004)

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. - Andris Ambainis; Ke Yang 005 (CCC, 2004)

Quantum Identification of Boolean Oracles. - Andris Ambainis; Kazuo Iwama; Akinori Kawachi; Hiroyuki Masuda; Raymond H. Putra; Shigeru Yamashita (STACS, 2004)

Quantum algorithms a decade after shor. - Andris Ambainis (STOC, 2004)

Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance - Andris Ambainis; William I. Gasarch; Aravind Srinivasan; Andrey Utis (CoRR, 2004)

Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna - Andris Ambainis; William I. Gasarch; Aravind Srinivasan; Andrey Utis (Electron. Colloquium Comput. Complex., 2004)

A new protocol and lower bounds for quantum coin flipping. - Andris Ambainis (J. Comput. Syst. Sci., 2004)

Parsimony hierarchies for inductive inference. - Andris Ambainis; John Case; Sanjay Jain 001; Mandayam Suraj (J. Symb. Log., 2004)

Distributed construction of quantum fingerprints. - Andris Ambainis; Yaoyun Shi (Quantum Inf. Comput., 2004)

Quantum search algorithms. - Andris Ambainis (SIGACT News, 2004)

Coins make quantum walks faster. - Andris Ambainis; Julia Kempe; Alexander Rivosh (SODA, 2005)

Quantum Search of Spatial Regions. - Scott Aaronson; Andris Ambainis (Theory Comput., 2005)

Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. - Andris Ambainis (Theory Comput., 2005)

Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems. - Andris Ambainis; William I. Gasarch; Aravind Srinivasan; Andrey Utis (ISAAC, 2006)

Quantum Algorithms for Matching and Network Flows. - Andris Ambainis; Robert Spalek (STACS, 2006)

Computing with highly mixed states. - Andris Ambainis; Leonard J. Schulman; Umesh V. Vazirani (J. ACM, 2006)

Polynomial degree vs. quantum query complexity. - Andris Ambainis (J. Comput. Syst. Sci., 2006)

Algebraic Results on Quantum Automata. - Andris Ambainis; Martin Beaudry; Marats Golovkins; Arnolds Kikusts; Mark Mercer; Denis Thérien (Theory Comput. Syst., 2006)

The minimum distance problem for two-way entanglement purification. - Andris Ambainis; Daniel Gottesman (IEEE Trans. Inf. Theory, 2006)

Quantum t-designs: t-wise independence in the quantum world. - Andris Ambainis; Joseph Emerson (Electron. Colloquium Comput. Complex., 2007)

Quantum Walk Algorithm for Element Distinctness. - Andris Ambainis (SIAM J. Comput., 2007)

Improved algorithms for quantum identification of Boolean oracles. - Andris Ambainis; Kazuo Iwama; Akinori Kawachi; Rudy Raymond; Shigeru Yamashita (Theor. Comput. Sci., 2007)

Quantum Query Complexity of Boolean Functions with Small On-Sets. - Andris Ambainis; Kazuo Iwama; Masaki Nakanishi; Harumichi Nishimura; Rudy Raymond; Seiichiro Tani; Shigeru Yamashita (ISAAC, 2008)

Quantum Random Walks - New Method for Designing Quantum Algorithms. - Andris Ambainis (SOFSEM, 2008)

Quantum Walks with Multiple or Moving Marked Locations. - Andris Ambainis; Alexander Rivosh (SOFSEM, 2008)

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

Quantum Algorithm for Element Distinctness. - Andris Ambainis (Encyclopedia of Algorithms, 2008)

Quantum Algorithm for Search on Grids. - Andris Ambainis (Encyclopedia of Algorithms, 2008)

A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. - Andris Ambainis; Robert Spalek; Ronald de Wolf (Algorithmica, 2009)

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size - Andris Ambainis; Kazuo Iwama; Masaki Nakanishi; Harumichi Nishimura; Rudy Raymond; Seiichiro Tani; Shigeru Yamashita (CoRR, 2009)

The Need for Structure in Quantum Speedups. - Scott Aaronson; Andris Ambainis (Electron. Colloquium Comput. Complex., 2009)

Improved constructions of quantum automata. - Andris Ambainis; Nikolajs Nahimovs (Theor. Comput. Sci., 2009)

New Developments in Quantum Algorithms. - Andris Ambainis (MFCS, 2010)

Nonlocal Quantum XOR Games for Large Number of Players. - Andris Ambainis; Dmitry Kravchenko; Nikolajs Nahimovs; Alexander Rivosh (TAMC, 2010)

Quantum algorithms for formula evaluation - Andris Ambainis (CoRR, 2010)

Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations - Andris Ambainis (CoRR, 2010)

Symmetry-assisted adversaries for quantum state generation. - Andris Ambainis; Loïck Magnin; Martin Roetteler; Jérémie Roland (Electron. Colloquium Comput. Complex., 2010)

Quantum Search with Variable Times. - Andris Ambainis (Theory Comput. Syst., 2010)

Limits on entropic uncertainty relations. - Andris Ambainis (Quantum Inf. Comput., 2010)

The quantum query complexity of certification. - Andris Ambainis; Andrew M. Childs; François Le Gall; Seiichiro Tani (Quantum Inf. Comput., 2010)

Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1) on a Quantum Computer. - Andris Ambainis; Andrew M. Childs; Ben Reichardt; Robert Spalek; Shengyu Zhang (SIAM J. Comput., 2010)

A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. - Andris Ambainis (Theory Comput., 2010)

Quantum algorithms for formula evaluation. - Andris Ambainis (Quantum Cryptography and Computing, 2010)

Quantum Property Testing for Bounded-Degree Graphs. - Andris Ambainis; Andrew M. Childs; Yi-Kai Liu 001 (APPROX-RANDOM, 2011)

Quantum Finite Automata. - Andris Ambainis (NCMA, 2011)

New separation between $s(f)$ and $bs(f)$ - Andris Ambainis; Xiaoming Sun 001 (CoRR, 2011)

Quantum strategies are better than classical in almost any XOR game - Andris Ambainis; Arturs Backurs; Kaspars Balodis; Dmitry Kravchenko; Raitis Ozols; Juris Smotrovs; Madars Virza (CoRR, 2011)

New separation between s(f) and bs(f). - Andris Ambainis; Xiaoming Sun 001 (Electron. Colloquium Comput. Complex., 2011)

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 (ICALP (1), 2012)

Grover's Algorithm with Errors. - Andris Ambainis; Arturs Backurs; Nikolajs Nahimovs; Alexander Rivosh (MEMICS, 2012)

Advantage of Quantum Strategies in Random Symmetric XOR Games. - Andris Ambainis; Janis Iraids; Dmitry Kravchenko; Madars Virza (MEMICS, 2012)

Variable time amplitude amplification and quantum algorithms for linear algebra problems. - Andris Ambainis (STACS, 2012)

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. - Andris Ambainis; Arturs Backurs; Nikolajs Nahimovs; Raitis Ozols; Alexander Rivosh (TQC, 2012)

Superiority of exact quantum automata for promise problems. - Andris Ambainis; Abuzer Yakaryilmaz (Inf. Process. Lett., 2012)

A quantum lovász local lemma. - Andris Ambainis; Julia Kempe; Or Sattath (J. ACM, 2012)

Worst Case Analysis of Non-local Games. - Andris Ambainis; Arturs Backurs; Kaspars Balodis; Agnis Skuskovniks; Juris Smotrovs; Madars Virza (SOFSEM, 2013)

Optimal quantum query bounds for almost all Boolean functions. - Andris Ambainis; Arturs Backurs; Juris Smotrovs; Ronald de Wolf (STACS, 2013)

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. - Andris Ambainis; Janis Iraids (TQC, 2013)

Exact Quantum Query Complexity of EXACT and THRESHOLD. - Andris Ambainis; Janis Iraids; Juris Smotrovs (TQC, 2013)

New upper bound on block sensitivity and certificate complexity in terms of sensitivity. - Andris Ambainis; Yihan Gao; Jieming Mao; Xiaoming Sun 001; Song Zuo (CoRR, 2013)

Parameterized Quantum Query Complexity of Graph Collision - Andris Ambainis; Kaspars Balodis; Janis Iraids; Raitis Ozols; Juris Smotrovs (CoRR, 2013)

Weak Parity. - Scott Aaronson; Andris Ambainis; Kaspars Balodis; Mohammad Bavarian (Electron. Colloquium Comput. Complex., 2013)

On symmetric nonlocal games. - Andris Ambainis; Dmitry Kravchenko; Nikolay Nahimov; Alexander Rivosh; Madars Virza (Theor. Comput. Sci., 2013)

On Physical Problems that are Slightly More Difficult than QMA. - Andris Ambainis (CCC, 2014)

Recent Developments in Quantum Algorithms and Complexity. - Andris Ambainis (DCFS, 2014)

How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? - Andris Ambainis; Ronald de Wolf (Comput. Complex., 2014)

Exact query complexity of some special classes of Boolean functions. - Andris Ambainis; Jozef Gruska; Shenggen Zheng (CoRR, 2014)

Tighter Relations Between Sensitivity and Other Complexity Measures. - Andris Ambainis; Mohammad Bavarian; Yihan Gao; Jieming Mao; Xiaoming Sun 001; Song Zuo (Electron. Colloquium Comput. Complex., 2014)

Fast Matrix Multiplication: Limitations of the Laser Method. - Andris Ambainis; Yuval Filmus; François Le Gall (Electron. Colloquium Comput. Complex., 2014)

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. - Andris Ambainis; Krisjanis Prusis (Electron. Colloquium Comput. Complex., 2014)

Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. - Andris Ambainis; Jevgenijs Vihrovs (Electron. Colloquium Comput. Complex., 2014)

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. - Andris Ambainis; Ansis Rosmanis; Dominique Unruh (IACR Cryptol. ePrint Arch., 2014)

Quantum algorithms for search with wildcards and combinatorial group testing. - Andris Ambainis; Ashley Montanaro (Quantum Inf. Comput., 2014)

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. - Andris Ambainis; Yuval Filmus; François Le Gall (STOC, 2015)

Almost quadratic gap between partition complexity and query/communication complexity. - Andris Ambainis; Martins Kokainis (CoRR, 2015)

Optimal Classical Random Access Codes Using Single d-level Systems. - Andris Ambainis; Dmitry Kravchenko; Ashutosh Rai 002 (CoRR, 2015)

Automata and Quantum Computing. - Andris Ambainis; Abuzer Yakaryilmaz (CoRR, 2015)

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. - Andris Ambainis (Electron. Colloquium Comput. Complex., 2015)

Almost quadratic gap between partition complexity and query/communication complexity. - Andris Ambainis (Electron. Colloquium Comput. Complex., 2015)

Separations in Query Complexity Based on Pointer Functions. - Andris Ambainis; Kaspars Balodis; Aleksandrs Belovs; Troy Lee; Miklos Santha; Juris Smotrovs (Electron. Colloquium Comput. Complex., 2015)

Exact quantum algorithms have advantage for almost all Boolean functions. - Andris Ambainis; Jozef Gruska; Shenggen Zheng (Quantum Inf. Comput., 2015)

Spatial search on grids with minimum memory. - Andris Ambainis; Renato Portugal; Nikolay Nahimov (Quantum Inf. Comput., 2015)

Correcting for potential barriers in quantum walk search. - Andris Ambainis; Thomas G. Wong (Quantum Inf. Comput., 2015)

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems. - Andris Ambainis; William I. Gasarch; Aravind Srinivasan; Andrey Utis (ACM Trans. Comput. Theory, 2015)

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. - Scott Aaronson; Andris Ambainis; Janis Iraids; Martins Kokainis; Juris Smotrovs (CCC, 2016)

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. - Andris Ambainis; Martins Kokainis; Robin Kothari (CCC, 2016)

Sensitivity Versus Certificate Complexity of Boolean Functions. - Andris Ambainis; Krisjanis Prusis; Jevgenijs Vihrovs (CSR, 2016)

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. - Andris Ambainis; Aleksandrs Belovs; Oded Regev 001; Ronald de Wolf (SODA, 2016)

Four Collaborations with Rūsiņš Freivalds. - Andris Ambainis (Balt. J. Mod. Comput., 2016)

Optimal One-shot Quantum Algorithm for EQUALITY and AND. - Andris Ambainis; Janis Iraids (Balt. J. Mod. Comput., 2016)

Quantum Query Complexity of Almost All Functions with Fixed On-set Size. - Andris Ambainis; Kazuo Iwama; Masaki Nakanishi; Harumichi Nishimura; Rudy Raymond; Seiichiro Tani; Shigeru Yamashita (Comput. Complex., 2016)

Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. - Andris Ambainis; Manik Banik; Anubhav Chaturvedi; Dmitry Kravchenko; Ashutosh Rai 002 (CoRR, 2016)

Exact quantum query complexity of EXACTk, ln. - Andris Ambainis; Janis Iraids; Daniel Nagaj (CoRR, 2016)

Rūsiņš Mārtiņš Freivalds (1942-2016). - Andris Ambainis (Bull. EATCS, 2016)

Superlinear Advantage for Exact Quantum Algorithms. - Andris Ambainis (SIAM J. Comput., 2016)

Quantum Algorithm for Element Distinctness. - Andris Ambainis (Encyclopedia of Algorithms, 2016)

Quantum Algorithm for Search on Grids. - Andris Ambainis (Encyclopedia of Algorithms, 2016)

Exact Quantum Query Complexity of text EXACT_k, l^n. - Andris Ambainis; Janis Iraids; Daniel Nagaj (SOFSEM, 2017)

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. - Andris Ambainis; Martins Kokainis (STOC, 2017)

Understanding Quantum Algorithms via Query Complexity. - Andris Ambainis (CoRR, 2017)

All Classical Adversary Methods are Equivalent for Total Functions. - Andris Ambainis; Martins Kokainis; Krisjanis Prusis; Jevgenijs Vihrovs (Electron. Colloquium Comput. Complex., 2017)

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 (SOFSEM, 2018)

On Block Sensitivity and Fractional Block Sensitivity. - Andris Ambainis; Krisjanis Prusis; Jevgenijs Vihrovs (CoRR, 2018)

Quantum security proofs using semi-classical oracles. - Andris Ambainis; Mike Hamburg; Dominique Unruh (IACR Cryptol. ePrint Arch., 2018)

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. - Scott Aaronson; Andris Ambainis (SIAM J. Comput., 2018)

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. - Andris Ambainis; Kaspars Balodis; Janis Iraids; Martins Kokainis; Krisjanis Prusis; Jevgenijs Vihrovs (SODA, 2019)

Quantum Lower Bounds for 2D-Grid and Dyck Language. - Andris Ambainis; Kaspars Balodis; Janis Iraids; Krisjanis Prusis; Juris Smotrovs (CoRR, 2019)

Parity oblivious d-level random access codes and class of noncontextuality inequalities. - Andris Ambainis; Manik Banik; Anubhav Chaturvedi; Dmitry Kravchenko; Ashutosh Rai 002 (Quantum Inf. Process., 2019)

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 001; Juris Smotrovs; Jevgenijs Vihrovs (MFCS, 2020)

Quadratic speedup for finding marked vertices by quantum walks. - Andris Ambainis; András Gilyén; Stacey Jeffery; Martins Kokainis (STOC, 2020)

Quantum Algorithms for Computational Geometry Problems. - Andris Ambainis; Nikita Larka (TQC, 2020)

Automata and quantum computing. - Andris Ambainis; Abuzer Yakaryilmaz (Handbook of Automata Theory (II.), 2021)

A Note About Claw Function with a Small Range. - Andris Ambainis; Kaspars Balodis; Janis Iraids (TQC, 2021)

On quantum versus classical query complexity. - Scott Aaronson; Andris Ambainis; Andrej Bogdanov; Krishnamoorthy Dinesh 001; Tsun Ming Cheung (Electron. Colloquium Comput. Complex., 2021)

All Classical Adversary Methods Are Equivalent for Total Functions. - Andris Ambainis; Martins Kokainis; Krisjanis Prusis; Jevgenijs Vihrovs; Aleksejs Zajakins (ACM Trans. Comput. Theory, 2021)

Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. - Andris Ambainis; Harry Buhrman; Koen Leijnse; Subhasree Patro; Florian Speelman (CoRR, 2022)

Dataset for "Strong dispersion property for the quantum walk on the hypercube". - Martins Kokainis; Krisjanis Prusis; Jevgenijs Vihrovs; Vyacheslavs Kashcheyevs; Andris Ambainis (Zenodo, 2022)

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. - Andris Ambainis; Aleksandrs Belovs (CCC, 2023)

Quantum Complexity for Vector Domination Problem. - Andris Ambainis; Ansis Zvirbulis (SOFSEM, 2023)

Improved Algorithm and Lower Bound for Variable Time Quantum Search. - Andris Ambainis; Martins Kokainis; Jevgenijs Vihrovs (TQC, 2023)

Quantum bounds for 2D-grid and Dyck language. - Andris Ambainis; Kaspars Balodis; Janis Iraids; Kamil Khadiev; Vladislavs Klevickis; Krisjanis Prusis; Yixin Shen 001; Juris Smotrovs; Jevgenijs Vihrovs (Quantum Inf. Process., 2023)

A hybrid quantum-classical approach for inference on restricted Boltzmann machines. - Martins Kalis; Andris Locans; Rolands Sikovs; Hassan Naseri; Andris Ambainis (Quantum Mach. Intell., 2023)

Quantum Algorithm for the Domatic Number Problem. - Andris Ambainis; Ilja Repko (Balt. J. Mod. Comput., 2024)

Quantum Search on Bipartite Multigraphs. - Gustavo Alves Bezerra; Andris Ambainis; Renato Portugal (CoRR, 2025)

Quantum computing and artificial intelligence: status and perspectives. - 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; et al. (CoRR, 2025)

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model. - Andris Ambainis; João F. Doriguello; Debbie Lim (CoRR, 2025)