Andris Ambainis

ORCID

Publication Activity (10 Years)

Years Active: 1994-2023
Publications (10 Years): 47

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

TQC

Publications

Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
Quantum bounds for 2D-grid and Dyck language. Quantum Inf. Process. 22 (5) (2023)
Andris Ambainis, Martins Kokainis, Jevgenijs Vihrovs
Improved Algorithm and Lower Bound for Variable Time Quantum Search. TQC (2023)
Martins Kalis, Andris Locans, Rolands Sikovs, Hassan Naseri, Andris Ambainis
A hybrid quantum-classical approach for inference on restricted Boltzmann machines. CoRR (2023)
Andris Ambainis, Aleksandrs Belovs
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC (2023)
Andris Ambainis, Ansis Zvirbulis
Quantum Complexity for Vector Domination Problem. SOFSEM (2023)
Martins Kalis, Andris Locans, Rolands Sikovs, Hassan Naseri, Andris Ambainis
A hybrid quantum-classical approach for inference on restricted Boltzmann machines. Quantum Mach. Intell. 5 (2) (2023)
Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR (2022)
Andris Ambainis, Kaspars Balodis, Janis Iraids
A note about claw function with a small range. CoRR (2021)
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, Aleksejs Zajakins
All Classical Adversary Methods Are Equivalent for Total Functions. ACM Trans. Comput. Theory 13 (1) (2021)
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Andris Ambainis, Kaspars Balodis, Janis Iraids
A Note About Claw Function with a Small Range. TQC (2021)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. CoRR (2020)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, Jevgenijs Vihrovs
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. MFCS (2020)
Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis
Quadratic speedup for finding marked vertices by quantum walks. STOC (2020)
Andris Ambainis, Nikita Larka
Quantum algorithms for computational geometry problems. CoRR (2020)
Andris Ambainis, Nikita Larka
Quantum Algorithms for Computational Geometry Problems. TQC (2020)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA (2019)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Krisjanis Prusis, Juris Smotrovs
Quantum Lower Bounds for 2D-Grid and Dyck Language. CoRR (2019)
Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis
Quadratic speedup for finding marked vertices by quantum walks. CoRR (2019)
Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai
-level random access codes and class of noncontextuality inequalities. Quantum Inf. Process. 18 (4) (2019)
Andris Ambainis, Mike Hamburg, Dominique Unruh
Quantum Security Proofs Using Semi-classical Oracles. CRYPTO (2) (2019)
Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
On Block Sensitivity and Fractional Block Sensitivity. CoRR (2018)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. 47 (3) (2018)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. CoRR (2018)
Farid M. Ablayev, Andris Ambainis, Kamil Khadiev, Aliya Khadieva
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test. SOFSEM (2018)
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
All Classical Adversary Methods are Equivalent for Total Functions. STACS (2018)
Andris Ambainis, Mike Hamburg, Dominique Unruh
Quantum security proofs using semi-classical oracles. IACR Cryptol. ePrint Arch. 2018 (2018)
Andris Ambainis, Janis Iraids, Daniel Nagaj
Exact Quantum Query Complexity of \text EXACT_k, l^n. SOFSEM (2017)
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
All Classical Adversary Methods are Equivalent for Total Functions. CoRR (2017)
Andris Ambainis
Understanding Quantum Algorithms via Query Complexity. CoRR (2017)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. J. ACM 64 (5) (2017)
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
All Classical Adversary Methods are Equivalent for Total Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Andris Ambainis, Janis Iraids
Optimal one-shot quantum algorithm for EQUALITY and AND. CoRR (2017)
Andris Ambainis, Martins Kokainis
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. CoRR (2017)
Andris Ambainis, Martins Kokainis
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. STOC (2017)
Andris Ambainis, Janis Iraids, Daniel Nagaj
. CoRR (2016)
Andris Ambainis
Four Collaborations with Rūsiņš Freivalds. Balt. J. Mod. Comput. 4 (4) (2016)
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
Quantum Query Complexity of Almost All Functions with Fixed On-set Size. Comput. Complex. 25 (4) (2016)
Andris Ambainis
Superlinear Advantage for Exact Quantum Algorithms. SIAM J. Comput. 45 (2) (2016)
Andris Ambainis, Martins Kokainis, Robin Kothari
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. Computational Complexity Conference (2016)
Andris Ambainis
Rūsiņš Mārtiņš Freivalds (1942-2016). Bull. EATCS 118 (2016)
Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
Sensitivity Versus Certificate Complexity of Boolean Functions. CSR (2016)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA (2016)
Andris Ambainis, Janis Iraids
Optimal One-shot Quantum Algorithm for EQUALITY and AND. Balt. J. Mod. Comput. 4 (4) (2016)
Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai
Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. CoRR (2016)
Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Computational Complexity Conference (2016)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in query complexity based on pointer functions. STOC (2016)
Andris Ambainis, Jevgenijs Vihrovs
Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. TAMC (2015)
Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR (2015)
Andris Ambainis
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Electron. Colloquium Comput. Complex. 22 (2015)
Andris Ambainis, Martins Kokainis
Almost quadratic gap between partition complexity and query/communication complexity. CoRR (2015)
Andris Ambainis, Dmitry Kravchenko, Ashutosh Rai
Optimal Classical Random Access Codes Using Single d-level Systems. CoRR (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC (2015)
Andris Ambainis, Abuzer Yakaryilmaz
Automata and Quantum Computing. CoRR (2015)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. STOC (2015)
Andris Ambainis, Thomas G. Wong
Correcting for potential barriers in quantum walk search. Quantum Inf. Comput. 15 (15&16) (2015)
Andris Ambainis
Almost quadratic gap between partition complexity and query/communication complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Andris Ambainis, Renato Portugal, Nikolay Nahimov
Spatial search on grids with minimum memory. Quantum Inf. Comput. 15 (13&14) (2015)
Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs
Sensitivity versus Certificate Complexity of Boolean Functions. CoRR (2015)
Andris Ambainis, Jozef Gruska, Shenggen Zheng
Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Inf. Comput. 15 (5&6) (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. CoRR (2015)
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems. ACM Trans. Comput. Theory 7 (3) (2015)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR (2015)
Andris Ambainis, Ronald de Wolf
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Comput. Complex. 23 (2) (2014)
Andris Ambainis, Ashley Montanaro
Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Inf. Comput. 14 (5-6) (2014)
Andris Ambainis, Krisjanis Prusis
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. MFCS (2) (2014)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. 21 (2014)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Laser Method. Electron. Colloquium Comput. Complex. 21 (2014)
Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
Tighter Relations between Sensitivity and Other Complexity Measures. ICALP (1) (2014)
Andris Ambainis
Recent Developments in Quantum Algorithms and Complexity. DCFS (2014)
Andris Ambainis, Ansis Rosmanis, Dominique Unruh
Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. FOCS (2014)
Scott Aaronson, Andris Ambainis
The Need for Structure in Quantum Speedups. Theory Comput. 10 (2014)
Andris Ambainis, Krisjanis Prusis
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Electron. Colloquium Comput. Complex. 21 (2014)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Laser Method. CoRR (2014)
Andris Ambainis, Ansis Rosmanis, Dominique Unruh
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. IACR Cryptol. ePrint Arch. 2014 (2014)
Andris Ambainis, Jevgenijs Vihrovs
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. CoRR (2014)
Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
Tighter Relations Between Sensitivity and Other Complexity Measures. Electron. Colloquium Comput. Complex. 21 (2014)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR (2014)
Andris Ambainis, Jevgenijs Vihrovs
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. Electron. Colloquium Comput. Complex. 21 (2014)
Andris Ambainis, Jozef Gruska, Shenggen Zheng
Exact query complexity of some special classes of Boolean functions. CoRR (2014)
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
Weak Parity. ICALP (1) (2014)
Krisjanis Prusis, Andris Ambainis
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. CoRR (2014)
Andris Ambainis
On Physical Problems that are Slightly More Difficult than QMA. Computational Complexity Conference (2014)
Andris Ambainis, Ansis Rosmanis, Dominique Unruh
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. CoRR (2014)
Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
Tighter Relations Between Sensitivity and Other Complexity Measures. CoRR (2014)
Andris Ambainis, Kaspars Balodis, Janis Iraids, Raitis Ozols, Juris Smotrovs
Parameterized Quantum Query Complexity of Graph Collision CoRR (2013)
Andris Ambainis
Superlinear advantage for exact quantum algorithms. STOC (2013)
Andris Ambainis, Janis Iraids, Juris Smotrovs
Exact Quantum Query Complexity of EXACT and THRESHOLD. TQC (2013)
Andris Ambainis
On physical problems that are slightly more difficult than QMA. CoRR (2013)
Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf
Optimal quantum query bounds for almost all Boolean functions. STACS (2013)
Andris Ambainis, Janis Iraids
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. TQC (2013)
Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov, Alexander Rivosh, Madars Virza
On symmetric nonlocal games. Theor. Comput. Sci. 494 (2013)
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
Weak Parity. CoRR (2013)
Andris Ambainis, Janis Iraids, Juris Smotrovs
Exact quantum query complexity of EXACT and THRESHOLD CoRR (2013)
Andris Ambainis, Ronald de Wolf
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? Computational Complexity Conference (2013)
Andris Ambainis, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo
New upper bound on block sensitivity and certificate complexity in terms of sensitivity. CoRR (2013)
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
Weak Parity. Electron. Colloquium Comput. Complex. 20 (2013)
Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza
Worst Case Analysis of Non-local Games. SOFSEM (2013)
Andris Ambainis
Superlinear advantage for exact quantum algorithms CoRR (2012)

Andris Ambainis.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Andris Ambainis