Papers

Accounts

Theses

PhD Thesis
Applications of the Adversary Method in Quantum Query Algorithms
University of Latvia, 2013. arXiv:1402.3858
Master's Thesis
Welch Bounds and Quantum State Tomography
University of Waterloo, 2008. Available here

Classical Computer Science

Preprints

Aleksandrs Belovs
Adaptive Lower Bound for Testing Monotonicity on the Line
arXiv:1801.08709

Publications

Aleksandrs Belovs, Gabor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang
On the polynomial parity argument complexity of the combinatorial Nullstellensatz
In Proceedings of the 32nd Computational Complexity Conference, volume 79 of LIPIcs, pages 30:1–30:24, 2017.
doi: 10.4230/LIPIcs.CCC.2017.30
preprint: arXiv:1710.08602
Aleksandrs Belovs and Eric Blais
A polynomial lower bound for testing monotonicity
In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 1021–1032, 2016.
doi: 10.1145/2897518.2897567
preprint: arXiv:1511.05053
Presented at Heilbronn and QALGO quantum algorithms meeting, Cambridge, April 2016. Slides.
Also presented at TCS+ video lecture series by Eric Blais, Video.
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions
In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 800–813, 2016.
doi: 10.1145/2897518.2897524
preprint: arXiv:1506.04719
Presented at QALGO 2015 project meeting, Riga, Latvia, September 2015,
Workshop on Semidefinite and Matrix Methods for Optimization and Communication, Singapore, January 2016, Slides.
Also presented as a plenary talk at QIP 2016, Banff, Alberta, Canada, January 2016 by Andris Ambinis.
Aleksandrs Belovs
Some Algebraic Properties of Machine Poset of Infinite Words
RAIRO Theoretical Informatics and Applications, 42(3), pages 451–466, 2008.
doi: 10.1051/ita:2008009
Aleksandrs Belovs
Non-Intersecting Complexity
In SOFSEM 2006: Theory and Practice of Computer Science,
volume 3831 of Lecture Notes in Computer Science, pages 158–165, Springer, 2006.
doi: 10.1007/11611257_13

Quantum Computer Science

Preprints

Aleksandrs Belovs
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem
arXiv:1712.10194
Aleksandrs Belovs, Gilles Brassard, Peter Hoyer, Marc Kaplan, Sophie Laplante, and Louis Salvail
Provably secure key establishment against quantum adversaries
arXiv:1704.08182
Chris Cade, Ashley Montanaro, and Aleksandrs Belovs
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness
arXiv:1610.00581
Aleksandrs Belovs
Variations on Quantum Adversary
arXiv:1504.06943
Aleksandrs Belovs and Ansis Rosmanis
On Adversary Lower Bounds for the Collision and the Set Equality Problems
arXiv:1310.5185
Aleksandrs Belovs
Quantum Walks and Electric Networks
arXiv:1302.3143
Merged with another submission, appeared as this paper
Aleksandrs Belovs and Troy Lee
Quantum Algorithm for k-Distinctness with Prior Knowledge on the Input
arXiv:1108.3022
Aleksandrs Belovs
Span-Program-Based Quantum Algorithm for the Rank Problem
arXiv:1103.0842

Publications

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha.
Separations in communication complexity using cheat sheets and information complexity
In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 555–564, 2016.
doi: 10.1109/FOCS.2016.66
preprint: arXiv:1605.01142
Aleksandrs Belovs, Juan Andres Montoya, and Abuzer Yakaryιlmaz
Looking for Pairs that Hard to Separate: A Quantum Approach
In Proceedings of the 21st International Conference on Implementation and Application of Automata (CIAA),
volume 9705 of Lecture Notes in Computer Science, pages 213–223, Springer, 2016.
doi: 10.1007/978-3-319-40946-7_18
preprint: arXiv:1602.07967
Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903–922, 2016.
preprint: arXiv:1507.03126
Also presented at QIP 2016, Banff, Alberta, Canada, January 2016 by Andris Ambinis.
Aleksandrs Belovs and Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube
Theory of Computing 11, pages 403-412, 2015.
doi: 10.4086/toc.2015.v011a016
preprint: arXiv:1503.02868
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan
Quantum lower bound for inverting a permutation with advice
Quantum Information & Computation, 15(11 & 12), pages 901-913, 2015.
preprint: arXiv:1408.3193
Aleksandrs Belovs
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
Computational Complexity 24(2), pages 255-293, 2015.
doi: 10.1007/s00037-015-0099-2
preprint: arXiv:1311.6777
Earlier in: Proceedings of the 29th IEEE Conference on Computational Complexity (CCC), pages 22-31, 2014. Slides
Best student paper award

Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Time-Efficient Quantum Walks for 3-Distinctness
In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Part I,
volume 7965 of Lecture Notes in Computer Science, pages 105–122, Springer, 2013.
doi: 10.1007/978-3-642-39206-1_10
Aleksandrs Belovs and Ansis Rosmanis
On the Power of Non-Adaptive Learning Graphs
Computational complexity 23(2), pages 323-354, 2014.
doi: 10.1007/s00037-014-0084-1
preprint: arXiv:1210.3279
Earlier in Proceedings of the 28th IEEE Conference on Computational Complexity (CCC), pages 44–55, 2013.
Best student paper award.
Also presented at Quantum and Crypto Day, Riga, Latvia, April 2013. Video.
Aleksandrs Belovs and Robert Špalek
Adversary Lower Bound for the k-Sum Problem
In Proceedings of the 4th ACM Innovations in Theoretical Computer Science conference (ITCS), pages 323–328, 2013.
doi: 10.1145/2422436.2422474
preprint: arXiv:1206.6528
Presented at QIP 2013, Beijing, China, January 2013, Video.
Aleksandrs Belovs
Learning-Graph-Based Quantum Algorithm for k-Distinctness
In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 207–216, 2012.
doi: 10.1109/FOCS.2012.18
preprint: arXiv:1205.1534
Presented at the Recent Progress in Quantum Algorithms Workshop, Waterloo, Canada, April 2012, Video;
and at QIP 2013, Beijing, China, January 2013, Video.
Aleksandrs Belovs and Ben W. Reichardt
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
In Proceedings of the 20th Annual European Symposium on Algorithms (ESA),
volume 7501 of Lecture Notes in Computer Science, pages 193–204, Springer, 2012.
doi: 10.1007/978-3-642-33090-2_18
preprint: arXiv:1203.2603
Presented at the Recent Progress in Quantum Algorithms Workshop, Waterloo, Canada, April 2012, by Ben Reichardt Video.
Aleksandrs Belovs
Span Programs for Functions With Constant-Sized 1-Certificates
In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 77–84, 2012.
doi: 10.1145/2213977.2213985
preprint: arXiv:1105.4024
Presented as a pleneary talk at QIP 2012, Montreal, Canada, December 2011. Video
Aleksandrs Belovs and Juris Smotrovs
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases
In Mathematical Methods in Computer Science: Essays in Memory of Thomas Beth,
volume 5393 of Lecture Notes in Computer Science, pages 50–69, Springer, 2008.
doi: 10.1007/978-3-540-89994-5_6
preprint: arXiv:0802.0855
Aleksandrs Belovs, Ansis Rosmanis, and Juris Smotrovs
Multi-Letter Reversible and Quantum Finite Automata
In Developments in Language Theory 2007,
volume 4588 of Lecture Notes in Computer Science, pages 60–71, Springer, 2007.
doi: 10.1007/978-3-540-73208-2_9