Publications

# Publications :: Search

## Show author

On this page you see the details of the selected author.

 Author information First name: Andris Last name: Ambainis DBLP: 70/5481 Rating: (not rated yet) Bookmark:

Below you find the publications which have been written by this author.

Show item 1 to 100 of 220
 Select a publication Show Title Venue Rating Date Conference paper Andris Ambainis, Janis Iraids, Daniel Nagaj. Exact Quantum Query Complexity of \text EXACT_k, l^n. SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings 2017 (0) 2017 Journal article Andris Ambainis, Janis Iraids. Optimal one-shot quantum algorithm for EQUALITY and AND. CoRR 2017, Volume 0 (0) 2017 Journal article Andris Ambainis, Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. CoRR 2017, Volume 0 (0) 2017 Journal article Andris Ambainis. RÅ«siÅ?Å¡ MÄ?rtiÅ?Å¡ Freivalds (1942-2016). Bulletin of the EATCS 2016, Volume 118 (0) 2016 Conference paper Andris Ambainis, Aleksandrs Belovs, Oded Regev 0001, Ronald de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 2016 (0) 2016 Conference paper Andris Ambainis. Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2016 (0) 2016 Conference paper Andris Ambainis. Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2016 (0) 2016 Conference paper Andris Ambainis. Superlinear Advantage for Exact Quantum Algorithms. SIAM J. Comput. 2016, Volume 45 (0) 2016 Conference paper Andris Ambainis, Martins Kokainis, Robin Kothari. Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan 2016 (0) 2016 Conference paper Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan 2016 (0) 2016 Conference paper Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs. Sensitivity Versus Certificate Complexity of Boolean Functions. Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings 2016 (0) 2016 Conference paper Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs. Separations in query complexity based on pointer functions. Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 2016 (0) 2016 Journal article Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai 0002. Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. CoRR 2016, Volume 0 (0) 2016 Journal article Andris Ambainis, Janis Iraids, Daniel Nagaj. Exact quantum query complexity of EXACT CoRR 2016, Volume 0 (0) 2016 Conference paper Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Raymond H. Putra, Seiichiro Tani, Shigeru Yamashita. Quantum Query Complexity of Almost All Functions with Fixed On-set Size. Computational Complexity 2016, Volume 25 (0) 2016 Conference paper Andris Ambainis, Jozef Gruska, Shenggen Zheng. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Information Computation 2015, Volume 15 (0) 2015 Journal article Andris Ambainis, Krisjanis Prusis, Jevgenijs Vihrovs. Sensitivity versus Certificate Complexity of Boolean Functions. CoRR 2015, Volume 0 (0) 2015 Conference paper Andris Ambainis, Jevgenijs Vihrovs. Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings 2015 (0) 2015 Conference paper Andris Ambainis, Yuval Filmus, François Le Gall. Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 2015 (0) 2015 Conference paper Scott Aaronson, Andris Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 2015 (0) 2015 Journal article Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. CoRR 2015, Volume 0 (0) 2015 Conference paper Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. Electronic Colloquium on Computational Complexity (ECCC) 2015, Volume 22 (0) 2015 Conference paper Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis. Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems. TOCT 2014, Volume 7 (0) 2015 Conference paper Andris Ambainis, Aleksandrs Belovs, Oded Regev 0001, Ronald de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR 2015, Volume 0 (0) 2015 Journal article Andris Ambainis, Abuzer Yakaryilmaz. Automata and Quantum Computing. CoRR 2015, Volume 0 (0) 2015 Conference paper Andris Ambainis, Renato Portugal, Nikolay Nahimov. Spatial search on grids with minimum memory. Quantum Information Computation 2015, Volume 15 (0) 2015 Conference paper Andris Ambainis, Thomas G. Wong. Correcting for potential barriers in quantum walk search. Quantum Information Computation 2015, Volume 15 (0) 2015 Conference paper Andris Ambainis, Dmitry Kravchenko, Ashutosh Rai 0002. Optimal Classical Random Access Codes Using Single d-level Systems. CoRR 2015, Volume 0 (0) 2015 Journal article Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR 2015, Volume 0 (0) 2015 Conference paper Andris Ambainis. Almost quadratic gap between partition complexity and query/communication complexity. Electronic Colloquium on Computational Complexity (ECCC) 2015, Volume 22 (0) 2015 Conference paper Andris Ambainis. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Electronic Colloquium on Computational Complexity (ECCC) 2015, Volume 22 (0) 2015 Journal article Andris Ambainis, Martins Kokainis. Almost quadratic gap between partition complexity and query/communication complexity. CoRR 2015, Volume 0 (0) 2015 Journal article Krisjanis Prusis, Andris Ambainis. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. CoRR 2014, Volume 0 (0) 2014 Conference paper Andris Ambainis, Krisjanis Prusis. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Electronic Colloquium on Computational Complexity (ECCC) 2014, Volume 21 (0) 2014 Journal article Andris Ambainis, Jozef Gruska, Shenggen Zheng. Exact query complexity of some special classes of Boolean functions. CoRR 2014, Volume 0 (0) 2014 Conference paper Andris Ambainis, Ansis Rosmanis, Dominique Unruh. Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. IACR Cryptology ePrint Archive 2014, Volume 2014 (0) 2014 Conference paper Andris Ambainis, Ronald de Wolf. How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Computational Complexity 2014, Volume 23 (0) 2014 Conference paper Andris Ambainis, Jevgenijs Vihrovs. Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. Electronic Colloquium on Computational Complexity (ECCC) 2014, Volume 21 (0) 2014 Conference paper Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian. Weak Parity. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 2014 (0) 2014 Conference paper Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo. Tighter Relations between Sensitivity and Other Complexity Measures. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 2014 (0) 2014 Journal article Andris Ambainis, Jevgenijs Vihrovs. Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. CoRR 2014, Volume 0 (0) 2014 Conference paper Andris Ambainis. Recent Developments in Quantum Algorithms and Complexity. Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings 2014 (0) 2014 Conference paper Andris Ambainis, Krisjanis Prusis. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II 2014 (0) 2014 Journal article Scott Aaronson, Andris Ambainis. The Need for Structure in Quantum Speedups. Theory of Computing 2014, Volume 10 (0) 2014 Conference paper Andris Ambainis. On Physical Problems that are Slightly More Difficult than QMA. IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014 2014 (0) 2014 Conference paper Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo. Tighter Relations Between Sensitivity and Other Complexity Measures. Electronic Colloquium on Computational Complexity (ECCC) 2014, Volume 21 (0) 2014 Journal article Andris Ambainis, Yuval Filmus, François Le Gall. Fast Matrix Multiplication: Limitations of the Laser Method. CoRR 2014, Volume 0 (0) 2014 Journal article Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo. Tighter Relations Between Sensitivity and Other Complexity Measures. CoRR 2014, Volume 0 (0) 2014 Journal article Scott Aaronson, Andris Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR 2014, Volume 0 (0) 2014 Conference paper Andris Ambainis, Ansis Rosmanis, Dominique Unruh. Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014 2014 (0) 2014 Conference paper Andris Ambainis, Ashley Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information Computation 2014, Volume 14 (0) 2014 Conference paper Andris Ambainis, Yuval Filmus, François Le Gall. Fast Matrix Multiplication: Limitations of the Laser Method. Electronic Colloquium on Computational Complexity (ECCC) 2014, Volume 21 (0) 2014 Conference paper Scott Aaronson, Andris Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electronic Colloquium on Computational Complexity (ECCC) 2014, Volume 21 (0) 2014 Conference paper Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza. Worst Case Analysis of Non-local Games. SOFSEM 2013 (0) 2013 Journal article Andris Ambainis, Janis Iraids, Juris Smotrovs. Exact quantum query complexity of EXACT and THRESHOLD CoRR 2013, Volume 0 (0) 2013 Conference paper Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf. Optimal quantum query bounds for almost all Boolean functions. 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany 2013 (0) 2013 Conference paper Andris Ambainis. Superlinear advantage for exact quantum algorithms. Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 2013 (0) 2013 Journal article Andris Ambainis, Kaspars Balodis, Janis Iraids, Raitis Ozols, Juris Smotrovs. Parameterized Quantum Query Complexity of Graph Collision CoRR 2013, Volume 0 (0) 2013 Journal article Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov, Alexander Rivosh, Madars Virza. On symmetric nonlocal games. Theor. Comput. Sci. 2013, Volume 494 (0) 2013 Conference paper 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, Volume 0 (0) 2013 Conference paper Andris Ambainis, Janis Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21-23, 2013, Guelph, Canada 2013 (0) 2013 Conference paper Andris Ambainis, Janis Iraids, Juris Smotrovs. Exact Quantum Query Complexity of EXACT and THRESHOLD. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21-23, 2013, Guelph, Canada 2013 (0) 2013 Conference paper Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian. Weak Parity. Electronic Colloquium on Computational Complexity (ECCC) 2013, Volume 20 (0) 2013 Journal article Andris Ambainis. On physical problems that are slightly more difficult than QMA. CoRR 2013, Volume 0 (0) 2013 Journal article Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian. Weak Parity. CoRR 2013, Volume 0 (0) 2013 Conference paper Andris Ambainis, Ronald de Wolf. How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013 2013 (0) 2013 Conference paper Andris Ambainis, Abuzer Yakaryilmaz. Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 2012, Volume 112 (0) 2012 Conference paper Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France 2012 (0) 2012 Conference paper 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. Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I 2012 (0) 2012 Conference paper Andris Ambainis, Julia Kempe, Or Sattath. A quantum lovász local lemma. J. ACM 2012, Volume 59 (0) 2012 Journal article Andris Ambainis. Superlinear advantage for exact quantum algorithms CoRR 2012, Volume 0 (0) 2012 Conference paper Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh. Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. TQC 2012 (0) 2012 Conference paper Andris Ambainis, Janis Iraids, Dmitry Kravchenko, Madars Virza. Advantage of Quantum Strategies in Random Symmetric XOR Games. Mathematical and Engineering Methods in Computer Science, 8th International Doctoral Workshop, MEMICS 2012, Znojmo, Czech Republic, October 25-28, 2012, Revised Selected Papers 2013 (0) 2012 Conference paper Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh. Grover's Algorithm with Errors. Mathematical and Engineering Methods in Computer Science, 8th International Doctoral Workshop, MEMICS 2012, Znojmo, Czech Republic, October 25-28, 2012, Revised Selected Papers 2013 (0) 2012 Conference paper Andris Ambainis, Loïck Magnin, Martin Rötteler, Jérémie Roland. Symmetry-Assisted Adversaries for Quantum State Generation. Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011 2011 (0) 2011 Conference paper Andris Ambainis, Andrew M. Childs, Yi-Kai Liu. Quantum Property Testing for Bounded-Degree Graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings 2011 (0) 2011 Conference paper Andris Ambainis, Xiaoming Sun. New separation between Electronic Colloquium on Computational Complexity (ECCC) 2011, Volume 18 (0) 2011 Journal article Andris Ambainis, Xiaoming Sun. New separation between $s(f)$ and $bs(f)$ CoRR 2011, Volume 0 (0) 2011 Conference paper Scott Aaronson, Andris Ambainis. The Need for Structure in Quantum Speedups. Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings 2011 (0) 2011 Conference paper Andris Ambainis. Quantum Finite Automata. Third Workshop on Non-Classical Models for Automata and Applications - NCMA 2011, Milan, Italy, July 18 - July 19, 2011. Proceedings 2011 (0) 2011 Conference paper Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh. Search by quantum walks on two-dimensional grid without amplitude amplification CoRR 2011, Volume 0 (0) 2011 Conference paper 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 2011, Volume 0 (0) 2011 Conference paper Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang. Any AND-OR Formula of Size N Can Be Evaluated in Time N SIAM J. Comput. 2009, Volume 39 (0) 2010 Conference paper Andris Ambainis, Julia Kempe, Or Sattath. A quantum lovász local lemma. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 2010 (0) 2010 Conference paper Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh. Nonlocal Quantum XOR Games for Large Number of Players. Theory and Applications of Models of Computation, 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings 2010 (0) 2010 Conference paper Andris Ambainis. Quantum Search with Variable Times. Theory Comput. Syst. 2010, Volume 47 (0) 2010 Journal article Andris Ambainis. Quantum algorithms for formula evaluation CoRR 2010, Volume 0 (0) 2010 Journal article Andris Ambainis. New Developments in Quantum Algorithms CoRR 2010, Volume 0 (0) 2010 Conference paper Andris Ambainis. New Developments in Quantum Algorithms. Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings 2010 (0) 2010 Journal article Andris Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations CoRR 2010, Volume 0 (0) 2010 Conference paper Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland. Symmetry-assisted adversaries for quantum state generation. Electronic Colloquium on Computational Complexity (ECCC) 2010, Volume 17 (0) 2010 Journal article Andris Ambainis, Loïck Magnin, Martin Rötteler, Jérémie Roland. Symmetry-assisted adversaries for quantum state generation CoRR 2010, Volume 0 (0) 2010 Journal article Andris Ambainis, Andrew M. Childs, Yi-Kai Liu. Quantum property testing for bounded-degree graphs CoRR 2010, Volume 0 (0) 2010 Journal article Andris Ambainis. A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. Theory of Computing 2010, Volume 6 (0) 2010 Conference paper Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani. The quantum query complexity of certification. Quantum Information Computation 2010, Volume 10 (0) 2010 Conference paper Andris Ambainis. Limits on entropic uncertainty relations. Quantum Information Computation 2010, Volume 10 (0) 2010 Conference paper Andris Ambainis. Quantum algorithms for formula evaluation. Quantum Cryptography and Computing 2010, Volume 26 (0) 2010 Journal article Scott Aaronson, Andris Ambainis. The Need for Structure in Quantum Speedups. Electronic Colloquium on Computational Complexity (ECCC) 2009, Volume 16 (0) 2009 Conference paper Andris Ambainis, Robert Spalek, Ronald de Wolf. A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 2009, Volume 55 (0) 2009 Conference paper Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani. The quantum query complexity of certification CoRR 2009, Volume 0 (0) 2009
Show item 1 to 100 of 220

Your query returned 220 matches in the database.