Aleksandrs Belovs

According to our database1, Aleksandrs Belovs authored at least 36 papers between 2003 and 2020.

Collaborative distances:



In proceedings 
PhD thesis 




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.
CoRR, 2017

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?
CoRR, 2016

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
CoRR, 2012

Adversary Lower Bound for Element Distinctness
CoRR, 2012

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
CoRR, 2011

Some Algebraic Properties of Machine Poset of Infinite Words.
ITA, 2008

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

Non-intersecting Complexity.
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