default search action
Andris 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
- 2024
- [j58]Andris Ambainis, Ilja Repko:
Quantum Algorithm for the Domatic Number Problem. Balt. J. Mod. Comput. 12(3) (2024) - 2023
- [j57]Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev
, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen
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
- [d1]Martins Kokainis
Dataset for "Strong dispersion property for the quantum walk on the hypercube". Zenodo, 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
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
Quadratic speedup for finding marked vertices by quantum walks. STOC 2020: 412-424 - [c99]Andris Ambainis
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
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
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
Separations in Query Complexity Based on Pointer Functions. J. ACM 64(5): 32:1-32:24 (2017) - [c94]Andris Ambainis, Janis Iraids
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
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
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
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
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
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
Worst Case Analysis of Non-local Games. SOFSEM 2013: 121-132 - [c76]Andris Ambainis, Arturs Backurs, Juris Smotrovs
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
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
A quantum lovász local lemma. J. ACM 59(5): 24:1-24:24 (2012) - [c72]Andris Ambainis, Arturs Backurs, Kaspars Balodis
Quantum Strategies Are Better Than Classical in Almost Any XOR Game. ICALP (1) 2012: 25-37 - [c71]Andris Ambainis, Janis Iraids
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
Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011: 365-376 - [c66]Andris Ambainis, Loïck Magnin, Martin Roetteler
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]Andris Ambainis, Andrew M. Childs
Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1) on a Quantum Computer. SIAM J. Comput. 39(6): 2513-2530 (2010) - [j32]Andris Ambainis:
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. Theory Comput. 6(1): 1-25 (2010) - [c63]Andris Ambainis:
New Developments in Quantum Algorithms. MFCS 2010: 1-11 - [c62]Andris Ambainis, Julia Kempe
A quantum lovász local lemma. STOC 2010: 151-160 - [c61]Andris Ambainis, Dmitry Kravchenko
Nonlocal Quantum XOR Games for Large Number of Players. TAMC 2010: 72-83 - [p1]Andris Ambainis:
Quantum algorithms for formula evaluation. Quantum Cryptography and Computing 2010: 115-124 - [i36]Andris Ambainis:
Quantum algorithms for formula evaluation. CoRR abs/1006.3651 (2010) - [i35]Andris Ambainis:
New Developments in Quantum Algorithms. CoRR abs/1006.4014 (2010) - [i34]Andris Ambainis:
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. CoRR abs/1010.4458 (2010) - [i33]Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland:
Symmetry-assisted adversaries for quantum state generation. CoRR abs/1012.2112 (2010) - [i32]Andris Ambainis, Andrew M. Childs, Yi-Kai Liu:
Quantum property testing for bounded-degree graphs. CoRR abs/1012.3174 (2010) - [i31]Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland:
Symmetry-assisted adversaries for quantum state generation. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j31]Andris Ambainis, Robert Spalek, Ronald de Wolf:
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422-461 (2009) - [j30]Andris Ambainis, Nikolajs Nahimovs:
Improved constructions of quantum automata. Theor. Comput. Sci. 410(20): 1916-1922 (2009) - [i30]Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani:
The quantum query complexity of certification. CoRR abs/0903.1291 (2009) - [i29]Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita:
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size. CoRR abs/0908.2468 (2009) - [i28]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. CoRR abs/0911.0996 (2009) - [i27]Andris Ambainis, Julia Kempe, Or Sattath:
A Quantum Lovasz Local Lemma. CoRR abs/0911.1696 (2009) - [i26]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j29]Andris Ambainis:
Probabilistic and team PFIN-type learning: General properties. J. Comput. Syst. Sci. 74(4): 457-489 (2008) - [c60]Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond
Quantum Query Complexity of Boolean Functions with Small On-Sets. ISAAC 2008: 907-918 - [c59]Andris Ambainis:
Quantum Random Walks - New Method for Designing Quantum Algorithms. SOFSEM 2008: 1-4 - [c58]Andris Ambainis, Alexander Rivosh:
Quantum Walks with Multiple or Moving Marked Locations. SOFSEM 2008: 485-496 - [c57]Andris Ambainis:
Quantum search with variable times. STACS 2008: 49-61 - [c56]Andris Ambainis, Nikolajs Nahimovs:
Improved Constructions of Quantum Automata. TQC 2008: 47-56 - [r2]Andris Ambainis:
Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2008 - [r1]Andris Ambainis:
Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2008 - 2007
- [j28]Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. SIAM J. Comput. 37(1): 210-239 (2007) - [j27]Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond
Improved algorithms for quantum identification of Boolean oracles. Theor. Comput. Sci. 378(1): 41-53 (2007) - [c55]Andris Ambainis, Joseph Emerson:
Quantum t-designs: t-wise Independence in the Quantum World. CCC 2007: 129-140 - [c54]Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang:
Any AND-OR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer. FOCS 2007: 363-372 - [i25]Andris Ambainis, Joseph Emerson:
Quantum t-designs: t-wise independence in the quantum world. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j26]Andris Ambainis, Leonard J. Schulman
Computing with highly mixed states. J. ACM 53(3): 507-531 (2006) - [j25]Andris Ambainis:
Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci. 72(2): 220-238 (2006) - [j24]Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien:
Algebraic Results on Quantum Automata. Theory Comput. Syst. 39(1): 165-188 (2006) - [j23]Andris Ambainis, Daniel Gottesman:
The minimum distance problem for two-way entanglement purification. IEEE Trans. Inf. Theory 52(2): 748-753 (2006) - [c53]Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis:
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems. ISAAC 2006: 628-637 - [c52]Andris Ambainis, Robert Spalek:
Quantum Algorithms for Matching and Network Flows. STACS 2006: 172-183 - [c51]Andris Ambainis, Robert Spalek, Ronald de Wolf:
A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. STOC 2006: 618-633 - [c50]Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond Harry Putra
Improved Algorithms for Quantum Identification of Boolean Oracles. SWAT 2006: 280-291 - 2005
- [j22]Andris Ambainis:
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. Theory Comput. 1(1): 37-46 (2005) - [j21]Scott Aaronson, Andris Ambainis:
Quantum Search of Spatial Regions. Theory Comput. 1(1): 47-79 (2005) - [c49]Andris Ambainis, Julia Kempe, Alexander Rivosh:
Coins make quantum walks faster. SODA 2005: 1099-1108 - [i24]Andris Ambainis:
Probabilistic and Team PFIN-type Learning: General Properties. CoRR abs/cs/0504001 (2005) - [i23]Andris Ambainis:
Quantum search algorithms. CoRR abs/quant-ph/0504012 (2005) - [i22]Andris Ambainis:
A new quantum lower bound method, with an application to strong direct product theorem for quantum search. CoRR abs/quant-ph/0508200 (2005) - [i21]Andris Ambainis, Robert Spalek, Ronald de Wolf:
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. CoRR abs/quant-ph/0511200 (2005) - 2004
- [j20]Andris Ambainis:
A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci. 68(2): 398-416 (2004) - [j19]Andris Ambainis, John Case, Sanjay Jain, Mandayam Suraj:
Parsimony hierarchies for inductive inference. J. Symb. Log. 69(1): 287-327 (2004) - [j18]Andris Ambainis, Yaoyun Shi:
Distributed construction of quantum fingerprints. Quantum Inf. Comput. 4(2): 146-151 (2004) - [j17]Andris Ambainis:
Quantum search algorithms. SIGACT News 35(2): 22-35 (2004) - [c48]Andris Ambainis, Adam D. Smith:
Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. APPROX-RANDOM 2004: 249-260 - [c47]Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig:
Multiparty Quantum Coin Flipping. CCC 2004: 250-259 - [c46]Andris Ambainis, Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. CCC 2004: 305-319 - [c45]Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. FOCS 2004: 22-31 - [c44]Andris Ambainis, Markus Jakobsson, Helger Lipmaa:
Cryptographic Randomized Response Techniques. Public Key Cryptography 2004: 425-438 - [c43]Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien:
Algebraic Results on Quantum Automata. STACS 2004: 93-104 - [c42]Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita:
Quantum Identification of Boolean Oracles. STACS 2004: 105-116 - [c41]Andris Ambainis:
Quantum algorithms a decade after shor. STOC 2004: 111 - [i20]Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance. CoRR cs.CC/0411076 (2004) - [i19]Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j16]Andris Ambainis, Leonard J. Schulman
The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32(6): 1570-1585 (2003) - [j15]Andris Ambainis, Arnolds Kikusts:
Exact results for accepting probabilities of quantum automata. Theor. Comput. Sci. 295: 3-25 (2003) - [c40]Scott Aaronson, Andris Ambainis:
Quantum Search of Spatial Regions. FOCS 2003: 200-209 - [c39]Andris Ambainis:
Polynomial Degree vs. Quantum Query Complexity. FOCS 2003: 230-239 - [c38]Andris Ambainis, Uldis Barbans, Agnese Belousova, Aleksandrs Belovs, Ilze Dzelme, Girts Folkmanis, Rusins Freivalds, Peteris Ledins, Rihards Opmanis, Agnis Skuskovniks:
Size of Quantum Versus Deterministic Finite Automata. VLSI 2003: 303-308 - [i18]Andris Ambainis, Markus Jakobsson, Helger Lipmaa:
Cryptographic Randomized Response Techniques. CoRR cs.CC/0302025 (2003) - [i17]Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig:
Multiparty Quantum Coin Flipping. CoRR quant-ph/0304112 (2003) - [i16]Andris Ambainis:
Polynomial degree vs. quantum query complexity. CoRR quant-ph/0305028 (2003) - [i15]Andris Ambainis, Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. Electron. Colloquium Comput. Complex. TR03 (2003) - [i14]Andris Ambainis, Markus Jakobsson, Helger Lipmaa:
Cryptographic Randomized Response Techniques. IACR Cryptol. ePrint Arch. 2003: 27 (2003) - 2002
- [j14]Andris Ambainis, Stephen A. Bloch, David L. Schweizer:
Delayed Binary Search, or Playing Twenty Questions with a Procrastinator. Algorithmica 32(4): 641-651 (2002) - [j13]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma
Dense quantum coding and quantum finite automata. J. ACM 49(4): 496-511 (2002) - [j12]Andris Ambainis:
Quantum Lower Bounds by Quantum Arguments. J. Comput. Syst. Sci. 64(4): 750-767 (2002) - [j11]Benjamin C. Travaglione, Michael A. Nielsen, Howard M. Wiseman, Andris Ambainis:
ROM-based computation: quantum versus classical. Quantum Inf. Comput. 2(4): 324-332 (2002) - [j10]Andris Ambainis, John Watrous:
Two-way finite automata with quantum and classical state. Theor. Comput. Sci. 287(1): 299-311 (2002) - [c37]Andris Ambainis, Adam D. Smith, Ke Yang:
Extracting Quantum Entanglement. CCC 2002: 103-112 - 2001
- [j9]Andris Ambainis:
On learning formulas in the limit and with assurance. Inf. Process. Lett. 77(1): 9-11 (2001) - [j8]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. J. Comput. Syst. Sci. 63(2): 148-185 (2001) - [j7]Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, Carl H. Smith:
Hierarchies of probabilistic and team FIN-learning. Theor. Comput. Sci. 261(1): 91-117 (2001) - [j6]Andris Ambainis:
Probabilistic inductive inference: a survey. Theor. Comput. Sci. 264(1): 155-167 (2001) - [c36]Andris Ambainis:
Quantum query algorithms and lower bounds. FotFS 2001: 15-32 - [c35]Andris Ambainis, Arnolds Kikusts:
Exact Results for Accepting Probabilities of Quantum Automata. MFCS 2001: 135-147 - [c34]Andris Ambainis, Arnolds Kikusts, Maris Valdats:
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. STACS 2001: 75-86 - [c33]Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous:
One-dimensional quantum walks. STOC 2001: 37-49 - [c32]Dorit Aharonov, Andris Ambainis, Julia Kempe
Quantum walks on graphs. STOC 2001: 50-59 - [c31]Andris Ambainis:
A new protocol and lower bounds for quantum coin flipping. STOC 2001: 134-142 - [i13]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j5]Andris Ambainis:
How rich is the structure of the intrinsic complexity of learning. Inf. Process. Lett. 75(3): 109-112 (2000) - [c30]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. CCC 2000: 44-53 - [c29]Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf:
Private Quantum Channels. FOCS 2000: 547-553 - [c28]Andris Ambainis, Satyanarayana V. Lokam:
Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. LATIN 2000: 207-216 - [c27]Andris Ambainis, Ronald de Wolf:
Average-Case Quantum Query Complexity. STACS 2000: 133-144 - [c26]Andris Ambainis:
Quantum lower bounds by quantum arguments. STOC 2000: 636-643 - [c25]Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani:
Computing with highly mixed states (extended abstract). STOC 2000: 697-704 - [i12]Andris Ambainis:
Quantum lower bounds by quantum arguments. CoRR quant-ph/0002066 (2000)
1990 – 1999
- 1999
- [j4]Andris Ambainis, Rusins Freivalds, Carl H. Smith:
Inductive Inference with Procrastination: Back to Definitions. Fundam. Informaticae 40(1): 1-16 (1999) - [j3]Andris Ambainis:
A Note on Quantum Black-Box Complexity of Almost all Boolean Functions. Inf. Process. Lett. 71(1): 5-7 (1999) - [j2]Andris Ambainis, Sanjay Jain, Arun Sharma:
Ordinal Mind Change Complexity of Language Identification. Theor. Comput. Sci. 220(2): 323-343 (1999) - [c24]Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts:
Probabilities to Accept Languages by Quantum Finite Automata. COCOON 1999: 174-183 - [c23]Andris Ambainis:
A Better Lower Bound for Quantum Algorithms Searching an Ordered List. FOCS 1999: 352-357 - [c22]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta
Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158 - [c21]Andris Ambainis, Stephen A. Bloch, David L. Schweizer:
Playing Twenty Questions with a Procrastinator. SODA 1999: 844-845 - [c20]Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski:
Quantum Finite Multitape Automata. SOFSEM 1999: 340-348 - [c19]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC 1999: 376-383 - [i11]Andris Ambainis, John Watrous:
Two-way finite automata with quantum and classical states. CoRR cs.CC/9911009 (1999) - [i10]Andris Ambainis:
Probabilistic Inductive Inference:a Survey. CoRR cs.LG/9902026 (1999) - [i9]Andris Ambainis:
A better lower bound for quantum algorithms searching an ordered list. CoRR quant-ph/9902053 (1999) - [i8]Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts:
Probabilities to accept languages by quantum finite automata. CoRR quant-ph/9904066 (1999) - [i7]Andris Ambainis, Ronald de Wolf:
Average-Case Quantum Query Complexity. CoRR quant-ph/9904079 (1999) - [i6]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [c18]Andris Ambainis, Rusins Freivalds:
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. FOCS 1998: 332-341 - [c17]Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma
The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351 - [c16]Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
On Counting AC0 Circuits with Negative Constants. MFCS 1998: 409-417 - [i5]Andris Ambainis, Rusins Freivalds:
1-way quantum finite automata: strengths, weaknesses and generalizations. CoRR quant-ph/9802062 (1998) - [i4]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata. CoRR quant-ph/9804043 (1998) - [i3]Andris Ambainis:
A note on quantum black-box complexity of almost all Boolean functions. CoRR quant-ph/9811080 (1998) - [i2]Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
On Counting AC0 Circuits with Negative Constants. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c15]Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, William I. Gasarch, Carl H. Smith:
Team Learning as a Game. ALT 1997: 2-17 - [c14]Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs
Effects of Kolmogorov Complexity Present in Inductive Inference as Well. ALT 1997: 244-259 - [c13]Andris Ambainis, Sanjay Jain, Arun Sharma:
Ordinal Mind Change Complexity of Language Identification. EuroCOLT 1997: 301-315 - [c12]Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan:
Nearly Tight Bounds on the Learnability of Evolution. FOCS 1997: 524-533 - [c11]Andris Ambainis:
Upper Bound on Communication Complexity of Private Information Retrieval. ICALP 1997: 401-407 - [c10]Andris Ambainis, Rusins Freivalds, Marek Karpinski:
Weak and Strong Recognition by 2-way Randomized Automata. RANDOM 1997: 175-185 - 1996
- [j1]Andris Ambainis:
Communication Complexity in a 3-Computer Model. Algorithmica 16(3): 298-301 (1996) - [c9]Andris Ambainis, Rusins Freivalds:
Transformations that Preserve Learnability. ALT 1996: 299-311 - [c8]Andris Ambainis:
Probabilistic and Team PFIN-Type Learning: General Properties. COLT 1996: 157-168 - [c7]Andris Ambainis:
The Complexity of Probabilistic versus Deterministic Finite Automata. ISAAC 1996: 233-238 - [c6]Andris Ambainis, Rusins Freivalds, Carl H. Smith:
General Inductive Inference Types Based on Linearly-Ordered Sets. STACS 1996: 243-253 - [c5]Andris Ambainis:
Upper Bounds on Multiparty Communication Complexity of Shifts. STACS 1996: 631-642 - [i1]Andris Ambainis:
Upper bound on the communication complexity of private information retrieval. IACR Cryptol. ePrint Arch. 1996: 6 (1996) - 1995
- [c4]Andris Ambainis:
Application of Kolmogorov Complexity to Inductive Inference with Limited Memory. ALT 1995: 313-318 - [c3]Andris Ambainis:
The power of procrastination in inductive inference: How it depends on used ordinal notations. EuroCOLT 1995: 99-111 - [c2]Andris Ambainis:
Optimization Problem in Inductive Inference. GOSLER Final Report 1995: 96-107 - 1994
- [c1]Andris Ambainis, Juris Smotrovs
Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference. AII/ALT 1994: 10-25
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-30 20:30 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: