According to our database1, Aleksandrs Belovs authored at least 36 papers between 2003 and 2020.
Legend:Book In proceedings Article PhD thesis Other
Testing convexity of functions over finite domains.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Quantum Dual Adversary for Hidden Subgroups and Beyond.
Proceedings of the Unconventional Computation and Natural Computation, 2019
Quantum Algorithms for Classical Probability Distributions.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019
Quantum Algorithm for Distribution-Free Junta Testing.
Proceedings of the Computer Science - Theory and Applications, 2019
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness.
Quantum Information & Computation, 2018
Adversary lower bounds for the collision and the set equality problems.
Quantum Information & Computation, 2018
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems.
Proceedings of the 13th Conference on the Theory of Quantum Computation, 2018
Adaptive Lower Bound for Testing Monotonicity on the Line.
Proceedings of the Approximation, 2018
Separations in Query Complexity Based on Pointer Functions.
J. ACM, 2017
On a Conjecture by Christian Choffrut.
Int. J. Found. Comput. Sci., 2017
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem.
Provably Secure Key Establishment Against Quantum Adversaries.
Proceedings of the 12th Conference on the Theory of Quantum Computation, 2017
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.
Proceedings of the 32nd Computational Complexity Conference, 2017
Quantum Algorithms for Graph Connectivity.
Encyclopedia of Algorithms, 2016
Separations in communication complexity using cheat sheets and information complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Can one quantum bit separate any pair of words with zero-error?
Looking for Pairs that Hard to Separate: A Quantum Approach.
Proceedings of the Implementation and Application of Automata, 2016
A polynomial lower bound for testing monotonicity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Quantum Algorithm for Monotonicity Testing on the Hypercube.
Theory of Computing, 2015
Quantum lower bound for inverting a permutation with advice.
Quantum Information & Computation, 2015
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound.
Computational Complexity, 2015
On the Power of Non-adaptive Learning Graphs.
Computational Complexity, 2014
Adversary lower bound for the k-sum problem.
Proceedings of the Innovations in Theoretical Computer Science, 2013
Time-Efficient Quantum Walks for 3-Distinctness.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013
On the Power of Non-Adaptive Learning Graphs
Adversary Lower Bound for Element Distinctness
Span programs for functions with constant-sized 1-certificates: extended abstract.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Learning-Graph-Based Quantum Algorithm for k-Distinctness.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection.
Proceedings of the Algorithms - ESA 2012, 2012
Span-program-based quantum algorithm for the rank problem
Some Algebraic Properties of Machine Poset of Infinite Words.
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases.
Proceedings of the Mathematical Methods in Computer Science, 2008
Multi-letter Reversible and Quantum Finite Automata.
Proceedings of the Developments in Language Theory, 11th International Conference, 2007
Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006
Size of Quantum Versus Deterministic Finite Automata.
Proceedings of the International Conference on VLSI, 2003