default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAndris Ambainis
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j57]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): 194 (2023)- [j56]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): 44 (2023) - [c105]Andris Ambainis, Aleksandrs Belovs:
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC 2023: 24:1-24:13 - [c104]Andris Ambainis, Ansis Zvirbulis:
Quantum Complexity for Vector Domination Problem. SOFSEM 2023: 328-341 - [c103]Andris Ambainis, Martins Kokainis, Jevgenijs Vihrovs:
Improved Algorithm and Lower Bound for Variable Time Quantum Search. TQC 2023: 7:1-7:18 - [i88]Martins Kalis, Andris Locans, Rolands Sikovs, Hassan Naseri, Andris Ambainis:
A hybrid quantum-classical approach for inference on restricted Boltzmann machines. CoRR abs/2304.12418 (2023) - 2022
- [i87]Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman:
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR abs/2207.11068 (2022) - 2021
- [j55]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): 7:1-7:20 (2021) - [c102]Andris Ambainis, Kaspars Balodis, Janis Iraids:
A Note About Claw Function with a Small Range. TQC 2021: 6:1-6:5 - [p2]Andris Ambainis, Abuzer Yakaryilmaz:
Automata and quantum computing. Handbook of Automata Theory (II.) 2021: 1457-1493 - [i86]Andris Ambainis, Kaspars Balodis, Janis Iraids:
A note about claw function with a small range. CoRR abs/2103.16390 (2021) - [i85]Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung:
On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c101]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: 8:1-8:14 - [c100]Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis:
Quadratic speedup for finding marked vertices by quantum walks. STOC 2020: 412-424 - [c99]Andris Ambainis, Nikita Larka:
Quantum Algorithms for Computational Geometry Problems. TQC 2020: 9:1-9:10 - [i84]Andris Ambainis, Nikita Larka:
Quantum algorithms for computational geometry problems. CoRR abs/2004.08949 (2020) - [i83]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 abs/2007.03402 (2020)
2010 – 2019
- 2019
- [j54]Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai:
Parity oblivious d-level random access codes and class of noncontextuality inequalities. Quantum Inf. Process. 18(4): 111 (2019) - [c98]Andris Ambainis, Mike Hamburg, Dominique Unruh:
Quantum Security Proofs Using Semi-classical Oracles. CRYPTO (2) 2019: 269-295 - [c97]Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019: 1783-1793 - [i82]Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis:
Quadratic speedup for finding marked vertices by quantum walks. CoRR abs/1903.07493 (2019) - [i81]Andris Ambainis, Kaspars Balodis, Janis Iraids, Krisjanis Prusis, Juris Smotrovs:
Quantum Lower Bounds for 2D-Grid and Dyck Language. CoRR abs/1911.12638 (2019) - 2018
- [j53]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. 47(3): 982-1038 (2018) - [c96]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: 197-211 - [c95]Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
All Classical Adversary Methods are Equivalent for Total Functions. STACS 2018: 8:1-8:14 - [i80]Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. CoRR abs/1807.05209 (2018) - [i79]Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs:
On Block Sensitivity and Fractional Block Sensitivity. CoRR abs/1810.02393 (2018) - [i78]Andris Ambainis, Mike Hamburg, Dominique Unruh:
Quantum security proofs using semi-classical oracles. IACR Cryptol. ePrint Arch. 2018: 904 (2018) - 2017
- [j52]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. J. ACM 64(5): 32:1-32:24 (2017) - [c94]Andris Ambainis, Janis Iraids, Daniel Nagaj:
Exact Quantum Query Complexity of \text EXACT_k, l^n. SOFSEM 2017: 243-255 - [c93]Andris Ambainis, Martins Kokainis:
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. STOC 2017: 989-1002 - [i77]Andris Ambainis, Janis Iraids:
Optimal one-shot quantum algorithm for EQUALITY and AND. CoRR abs/1701.06942 (2017) - [i76]Andris Ambainis, Martins Kokainis:
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. CoRR abs/1704.06774 (2017) - [i75]Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
All Classical Adversary Methods are Equivalent for Total Functions. CoRR abs/1709.08985 (2017) - [i74]Andris Ambainis:
Understanding Quantum Algorithms via Query Complexity. CoRR abs/1712.06349 (2017) - [i73]Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
All Classical Adversary Methods are Equivalent for Total Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j51]Andris Ambainis:
Four Collaborations with Rūsiņš Freivalds. Balt. J. Mod. Comput. 4(4) (2016) - [j50]Andris Ambainis, Janis Iraids:
Optimal One-shot Quantum Algorithm for EQUALITY and AND. Balt. J. Mod. Comput. 4(4) (2016) - [j49]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): 723-735 (2016) - [j48]Andris Ambainis:
Rūsiņš Mārtiņš Freivalds (1942-2016). Bull. EATCS 118 (2016) - [j47]Andris Ambainis:
Superlinear Advantage for Exact Quantum Algorithms. SIAM J. Comput. 45(2): 617-631 (2016) - [c92]Andris Ambainis, Martins Kokainis, Robin Kothari:
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. CCC 2016: 4:1-4:14 - [c91]Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CCC 2016: 25:1-25:19 - [c90]Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Sensitivity Versus Certificate Complexity of Boolean Functions. CSR 2016: 16-28 - [c89]Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf:
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA 2016: 903-922 - [c88]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in query complexity based on pointer functions. STOC 2016: 800-813 - [r4]Andris Ambainis:
Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2016: 1646-1651 - [r3]Andris Ambainis:
Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2016: 1656-1660 - [i72]Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai:
Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. CoRR abs/1607.05490 (2016) - [i71]Andris Ambainis, Janis Iraids, Daniel Nagaj:
Exact quantum query complexity of EXACTk, ln. CoRR abs/1608.02374 (2016) - 2015
- [j46]Andris Ambainis, Jozef Gruska, Shenggen Zheng:
Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Inf. Comput. 15(5&6): 435-452 (2015) - [j45]Andris Ambainis, Renato Portugal, Nikolay Nahimov:
Spatial search on grids with minimum memory. Quantum Inf. Comput. 15(13&14): 1233-1247 (2015) - [j44]Andris Ambainis, Thomas G. Wong:
Correcting for potential barriers in quantum walk search. Quantum Inf. Comput. 15(15&16): 1365-1372 (2015) - [j43]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): 10:1-10:10 (2015) - [c87]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC 2015: 307-316 - [c86]Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. STOC 2015: 585-593 - [c85]Andris Ambainis, Jevgenijs Vihrovs:
Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. TAMC 2015: 122-133 - [i70]Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Sensitivity versus Certificate Complexity of Boolean Functions. CoRR abs/1503.07691 (2015) - [i69]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. CoRR abs/1506.04719 (2015) - [i68]Andris Ambainis, Abuzer Yakaryilmaz:
Automata and Quantum Computing. CoRR abs/1507.01988 (2015) - [i67]Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf:
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR abs/1507.03126 (2015) - [i66]Andris Ambainis, Dmitry Kravchenko, Ashutosh Rai:
Optimal Classical Random Access Codes Using Single d-level Systems. CoRR abs/1510.03045 (2015) - [i65]Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR abs/1511.08682 (2015) - [i64]Andris Ambainis, Martins Kokainis:
Almost quadratic gap between partition complexity and query/communication complexity. CoRR abs/1512.00661 (2015) - [i63]Andris Ambainis:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Electron. Colloquium Comput. Complex. TR15 (2015) - [i62]Andris Ambainis:
Almost quadratic gap between partition complexity and query/communication complexity. Electron. Colloquium Comput. Complex. TR15 (2015) - [i61]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j42]Andris Ambainis, Ronald de Wolf:
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Comput. Complex. 23(2): 305-322 (2014) - [j41]Andris Ambainis, Ashley Montanaro:
Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Inf. Comput. 14(5-6): 439-453 (2014) - [j40]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. Theory Comput. 10: 133-166 (2014) - [c84]Andris Ambainis:
On Physical Problems that are Slightly More Difficult than QMA. CCC 2014: 32-43 - [c83]Andris Ambainis:
Recent Developments in Quantum Algorithms and Complexity. DCFS 2014: 1-4 - [c82]Andris Ambainis, Ansis Rosmanis, Dominique Unruh:
Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. FOCS 2014: 474-483 - [c81]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. ICALP (1) 2014: 26-38 - [c80]Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations between Sensitivity and Other Complexity Measures. ICALP (1) 2014: 101-113 - [c79]Andris Ambainis, Krisjanis Prusis:
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. MFCS (2) 2014: 33-44 - [i60]Krisjanis Prusis, Andris Ambainis:
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. CoRR abs/1402.5078 (2014) - [i59]Andris Ambainis, Jozef Gruska, Shenggen Zheng:
Exact query complexity of some special classes of Boolean functions. CoRR abs/1404.1684 (2014) - [i58]Andris Ambainis, Ansis Rosmanis, Dominique Unruh:
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. CoRR abs/1404.6898 (2014) - [i57]Andris Ambainis, Jevgenijs Vihrovs:
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. CoRR abs/1406.0073 (2014) - [i56]Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations Between Sensitivity and Other Complexity Measures. CoRR abs/1411.3419 (2014) - [i55]Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Laser Method. CoRR abs/1411.5414 (2014) - [i54]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR abs/1411.5729 (2014) - [i53]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. TR14 (2014) - [i52]Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations Between Sensitivity and Other Complexity Measures. Electron. Colloquium Comput. Complex. TR14 (2014) - [i51]Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Laser Method. Electron. Colloquium Comput. Complex. TR14 (2014) - [i50]Andris Ambainis, Krisjanis Prusis:
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Electron. Colloquium Comput. Complex. TR14 (2014) - [i49]Andris Ambainis, Jevgenijs Vihrovs:
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. Electron. Colloquium Comput. Complex. TR14 (2014) - [i48]Andris Ambainis, Ansis Rosmanis, Dominique Unruh:
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. IACR Cryptol. ePrint Arch. 2014: 296 (2014) - 2013
- [j39]Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov, Alexander Rivosh, Madars Virza:
On symmetric nonlocal games. Theor. Comput. Sci. 494: 36-48 (2013) - [c78]Andris Ambainis, Ronald de Wolf:
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? CCC 2013: 179-184 - [c77]Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza:
Worst Case Analysis of Non-local Games. SOFSEM 2013: 121-132 - [c76]Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf:
Optimal quantum query bounds for almost all Boolean functions. STACS 2013: 446-453 - [c75]Andris Ambainis:
Superlinear advantage for exact quantum algorithms. STOC 2013: 891-900 - [c74]Andris Ambainis, Janis Iraids:
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. TQC 2013: 146-156 - [c73]Andris Ambainis, Janis Iraids, Juris Smotrovs:
Exact Quantum Query Complexity of EXACT and THRESHOLD. TQC 2013: 263-269 - [i47]Andris Ambainis, Janis Iraids, Juris Smotrovs:
Exact quantum query complexity of EXACT and THRESHOLD. CoRR abs/1302.1235 (2013) - [i46]Andris Ambainis, Kaspars Balodis, Janis Iraids, Raitis Ozols, Juris Smotrovs:
Parameterized Quantum Query Complexity of Graph Collision. CoRR abs/1305.1021 (2013) - [i45]Andris Ambainis, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
New upper bound on block sensitivity and certificate complexity in terms of sensitivity. CoRR abs/1306.4466 (2013) - [i44]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. CoRR abs/1312.0036 (2013) - [i43]Andris Ambainis:
On physical problems that are slightly more difficult than QMA. CoRR abs/1312.4758 (2013) - [i42]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j38]Andris Ambainis, Abuzer Yakaryilmaz:
Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112(7): 289-291 (2012) - [j37]Andris Ambainis, Julia Kempe, Or Sattath:
A quantum lovász local lemma. J. ACM 59(5): 24:1-24:24 (2012) - [c72]Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs, Madars Virza:
Quantum Strategies Are Better Than Classical in Almost Any XOR Game. ICALP (1) 2012: 25-37 - [c71]Andris Ambainis, Janis Iraids, Dmitry Kravchenko, Madars Virza:
Advantage of Quantum Strategies in Random Symmetric XOR Games. MEMICS 2012: 57-68 - [c70]Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh:
Grover's Algorithm with Errors. MEMICS 2012: 180-189 - [c69]Andris Ambainis:
Variable time amplitude amplification and quantum algorithms for linear algebra problems. STACS 2012: 636-647 - [c68]Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh:
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. TQC 2012: 87-97 - [i41]Andris Ambainis:
Superlinear advantage for exact quantum algorithms. CoRR abs/1211.0721 (2012) - 2011
- [c67]Andris Ambainis, Andrew M. Childs, Yi-Kai Liu:
Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011: 365-376 - [c66]Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland:
Symmetry-Assisted Adversaries for Quantum State Generation. CCC 2011: 167-177 - [c65]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. ICS 2011: 338-352 - [c64]Andris Ambainis:
Quantum Finite Automata. NCMA 2011: 9-13 - [i40]Andris Ambainis, Xiaoming Sun:
New separation between $s(f)$ and $bs(f)$. CoRR abs/1108.3494 (2011) - [i39]Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs, Madars Virza:
Quantum strategies are better than classical in almost any XOR game. CoRR abs/1112.3330 (2011) - [i38]Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh:
Search by quantum walks on two-dimensional grid without amplitude amplification. CoRR abs/1112.3337 (2011) - [i37]Andris Ambainis, Xiaoming Sun:
New separation between s(f) and bs(f). Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j36]Andris Ambainis:
Quantum Search with Variable Times. Theory Comput. Syst. 47(3): 786-807 (2010) - [j35]Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani:
The quantum query complexity of certification. Quantum Inf. Comput. 10(3&4): 181-189 (2010) - [j34]Andris Ambainis:
Limits on entropic uncertainty relations. Quantum Inf. Comput. 10(9&10): 848-858 (2010) - [j33]