Aleksandrs Belovs

According to our database, Aleksandrs Belovs authored at least 43 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

A Direct Reduction from the Polynomial to the Adversary Method.

Aleksandrs Belovs

Proceedings of the 19th Conference on the Theory of Quantum Computation, 2024

Quantum Algorithms for Hopcroft's Problem.

Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

On the quantum time complexity of divide and conquer.

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

CoRR, 2023

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree.

Andris Ambainis, Aleksandrs Belovs

Proceedings of the 38th Computational Complexity Conference, 2023

2021

A Polynomial Lower Bound for Testing Monotonicity.

Aleksandrs Belovs, Eric Blais

SIAM J. Comput., 2021

Quantum communication complexity of distribution testing.

Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov

Quantum Inf. Comput., 2021

2020

The quantum query complexity of composition with a relation.

Aleksandrs Belovs, Troy Lee

CoRR, 2020

Quantum Coupon Collector.

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Testing convexity of functions over finite domains.

Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Quantum Dual Adversary for Hidden Subgroups and Beyond.

Aleksandrs Belovs

Proceedings of the Unconventional Computation and Natural Computation, 2019

Quantum Algorithms for Classical Probability Distributions.

Aleksandrs Belovs

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Quantum Algorithm for Distribution-Free Junta Testing.

Aleksandrs Belovs

Proceedings of the Computer Science - Theory and Applications, 2019

2018

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness.

Chris Cade, Ashley Montanaro, Aleksandrs Belovs

Quantum Inf. Comput., 2018

Adversary lower bounds for the collision and the set equality problems.

Aleksandrs Belovs, Ansis Rosmanis

Quantum Inf. Comput., 2018

Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems.

Aleksandrs Belovs, Ansis Rosmanis

Proceedings of the 13th Conference on the Theory of Quantum Computation, 2018

Adaptive Lower Bound for Testing Monotonicity on the Line.

Aleksandrs Belovs

Proceedings of the Approximation, 2018

2017

On a Conjecture by Christian Choffrut.

Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz

Int. J. Found. Comput. Sci., 2017

Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem.

Aleksandrs Belovs

CoRR, 2017

Provably Secure Key Establishment Against Quantum Adversaries.

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail

Proceedings of the 12th Conference on the Theory of Quantum Computation, 2017

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.

Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Quantum Algorithms for Graph Connectivity.

Aleksandrs Belovs

Encyclopedia of Algorithms, 2016

Separations in communication complexity using cheat sheets and information complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Electron. Colloquium Comput. Complex., 2016

Can one quantum bit separate any pair of words with zero-error?

Aleksandrs Belovs, Juan Andrés Montoya, Abuzer Yakaryilmaz

CoRR, 2016

Looking for Pairs that Hard to Separate: A Quantum Approach.

Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz

Proceedings of the Implementation and Application of Automata, 2016

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.

Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Quantum Algorithm for Monotonicity Testing on the Hypercube.

Aleksandrs Belovs, Eric Blais

Theory Comput., 2015

Separations in Query Complexity Based on Pointer Functions.

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Electron. Colloquium Comput. Complex., 2015

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound.

Aleksandrs Belovs

Comput. Complex., 2015

2014

Quantum lower bound for inverting a permutation with advice.

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Electron. Colloquium Comput. Complex., 2014

On the Power of Non-adaptive Learning Graphs.

Aleksandrs Belovs, Ansis Rosmanis

Comput. Complex., 2014

2013

Adversary lower bound for the k-sum problem.

Aleksandrs Belovs, Robert Spalek

Proceedings of the Innovations in Theoretical Computer Science, 2013

Time-Efficient Quantum Walks for 3-Distinctness.

Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

On the Power of Non-Adaptive Learning Graphs

Aleksandrs Belovs

CoRR, 2012

Adversary Lower Bound for Element Distinctness

Aleksandrs Belovs

CoRR, 2012

Span programs for functions with constant-sized 1-certificates: extended abstract.

Aleksandrs Belovs

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Learning-Graph-Based Quantum Algorithm for k-Distinctness.

Aleksandrs Belovs

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection.

Aleksandrs Belovs, Ben W. Reichardt

Proceedings of the Algorithms - ESA 2012, 2012

2011

Span-program-based quantum algorithm for the rank problem

Aleksandrs Belovs

CoRR, 2011

2008

Some Algebraic Properties of Machine Poset of Infinite Words.

Aleksandrs Belovs

RAIRO Theor. Informatics Appl., 2008

A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases.

Aleksandrs Belovs, Juris Smotrovs

Proceedings of the Mathematical Methods in Computer Science, 2008

2007

Multi-letter Reversible and Quantum Finite Automata.

Aleksandrs Belovs, Ansis Rosmanis, Juris Smotrovs

Proceedings of the Developments in Language Theory, 11th International Conference, 2007

2006

Non-intersecting Complexity.

Aleksandrs Belovs

Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

2003

Size of Quantum Versus Deterministic Finite Automata.

Andris Ambainis, Uldis Barbans, Agnese Belousova, Aleksandrs Belovs, Ilze Dzelme, Girts Folkmanis, Rusins Freivalds, Peteris Ledins, Rihards Opmanis, Agnis Skuskovniks

Proceedings of the International Conference on VLSI, 2003