Aleksandrs Belovs
Aleksandrs Belovs
assistant professor, University of Latvia
Verified email at inbox.lv - Homepage
Title
Cited by
Cited by
Year
Span programs for functions with constant-sized 1-certificates
A Belovs
Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012
802012
Learning-graph-based Quantum Algorithm for k-distinctness
A Belovs
arXiv preprint arXiv:1205.1534, 2012
692012
Separations in query complexity based on pointer functions
A Ambainis, K Balodis, A Belovs, T Lee, M Santha, J Smotrovs
Journal of the ACM (JACM) 64 (5), 1-24, 2017
582017
A polynomial lower bound for testing monotonicity
A Belovs, E Blais
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
492016
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
A Belovs, BW Reichardt
European Symposium on Algorithms, 193-204, 2012
422012
Time-efficient quantum walks for 3-distinctness
A Belovs, AM Childs, S Jeffery, R Kothari, F Magniez
International Colloquium on Automata, Languages, and Programming, 105-122, 2013
382013
Adversary lower bound for the k-sum problem
A Belovs, R Spalek
Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013
322013
On the power of non-adaptive learning graphs
A Belovs, A Rosmanis
computational complexity 23 (2), 323-354, 2014
252014
Multi-letter reversible and quantum finite automata
A Belovs, A Rosmanis, J Smotrovs
International Conference on Developments in Language Theory, 60-71, 2007
252007
Quantum walks and electric networks
A Belovs
arXiv preprint arXiv:1302.3143, 2013
232013
Separations in communication complexity using cheat sheets and information complexity
A Anshu, A Belovs, S Ben-David, M Göös, R Jain, R Kothari, T Lee, ...
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
212016
Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
A Belovs, T Lee
Arxiv preprint arXiv:1108.3022, 2011
212011
On a conjecture by Christian Choffrut
A Belovs, JA Montoya, A Yakaryılmaz
International Journal of Foundations of Computer Science 28 (05), 483-501, 2017
17*2017
Efficient quantum algorithms for (gapped) group testing and junta testing
A Ambainis, A Belovs, O Regev, R Wolf
Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete …, 2016
162016
Quantum algorithms for learning symmetric juntas via the adversary bound
A Belovs
computational complexity 24 (2), 255-293, 2015
162015
Span-program-based quantum algorithm for the rank problem
A Belovs
arXiv preprint arXiv:1103.0842, 2011
162011
Some algebraic properties of machine poset of infinite words
A Belovs
RAIRO-Theoretical Informatics and Applications-Informatique Théorique et …, 2008
162008
On the polynomial parity argument complexity of the combinatorial nullstellensatz
A Belovs, G Ivanyos, Y Qiao, M Santha, S Yang
arXiv preprint arXiv:1710.08602, 2017
132017
Quantum algorithm for monotonicity testing on the hypercube
A Belovs, E Blais
arXiv preprint arXiv:1503.02868, 2015
132015
Adversary lower bounds for the collision and the set equality problems
A Belovs, A Rosmanis
arXiv preprint arXiv:1310.5185, 2013
132013
The system can't perform the operation now. Try again later.
Articles 1–20